1 Divisibilité dans Z

1.1 Définitions
Définition 1.
1) Soient a et b deux entiers relatifs tels que a 6= 0.
On dit que a divise b ou que a est un diviseur de b si et seulement si il existe un entier relatif q tel que b = qa.
Il revient au même de dire que a divise b ou que b est divisible par a.
Quand a divise b, on écrit a|b et quand a ne divise pas b, on écrit a 6 | b.
2) Soient a et b deux entiers relatifs.
b est un multiple de a si et seulement si il existe un entier relatif q tel que b = qa.
Si de plus, a 6= 0, b est multiple de a si et seulement si a divise b.
Notation. Si a est un entier relatif, l’ensemble des multiples de a est l’ensemble des nombres de la forme qa où q est un
entier relatif. Il se note aZ :

aZ = {qa, q ∈ Z} = {. . . , −2a, −a, 0, a, 2a, . . .}.

De même, l’ensemble des diviseurs de a se note div(a) ou D(a).
Exemples. 2 divise 6 car 6 = 3 × 2 avec 3 entier relatif. 4 divise −4 car 4 = (−1) × (−4) avec −1 entier relatif. 1 divise 5
car 5 = 5 × 1 avec 5 entier relatif. 1 divise 0 car 0 = 0 × 1 avec 0 entier relatif. ❏

1.2 Propriétés de la divisibilité

Théorème 1.
1) ∀a ∈ Z∗ , a|(−a) et (−a)|a. ∀a ∈ Z, −a est un multiple de a et a est un multiple de −a.
2) ∀(a, b) ∈ Z × Z∗ , b|a ⇔ (−b)|a ⇔ b|(−a) ⇔ (−b)|(−a).
Démonstration .

1) Soit a un entier relatif non nul. −a = a × (−1) avec −1 ∈ Z. Donc, a|(−a). Ensuite, en appliquant le résultat précédent à l’entier
−a, on a aussi −a|a.
Soient a ∈ Z et b ∈ Z∗ . Si b|a, il existe q ∈ Z tel que a = bq. Mais alors, a = (−b)(−q) avec −q ∈ Z et donc −b divise a. Ensuite,en
appliquant à l’entier relatif non nul −b, on a aussi le fait que si −b|a, alors b|a.
Enfin, en appliquant aux entiers ±a et/ou ±b, on obtient les deux autres équivalences.
❏

Théorème 2.
1) ∀a ∈ Z, les diviseurs de a sont les diviseurs de |a|.
2) ∀a ∈ Z, les multiples de a sont les multiples de |a|.
Démonstration .

1) Soit a ∈ Z. D’après le théorème 1, si b est un entier relatif divisant a, alors b divise a et −a et donc b divise |a|. Inversement, si
b est un entier relatif divisant |a|, b divise a qui est l’un des deux entiers |a| ou −|a|.
2) Soit a ∈ Z. Si b = qa, q ∈ Z, alors b = (sgn(a)q)|a| avec sgn(a)q ∈ Z et si b = q|a|, q ∈ Z, alors b = (sgn(a)q)a.
❏

Dans le théorème qui suit, 6 désigne la relation d’ordre usuelle dans N∗ ou Z∗ .

Théorème 3.
Soit a ∈ N∗ . ∀b ∈ N∗ , (b|a ⇒ b 6 a) (tout diviseur de a dans N∗ est inférieur ou égal à a).
Soit a ∈ N∗ . ∀b ∈ Z∗ , (b|a ⇒ b 6 a) (tout diviseur de a dans Z∗ est inférieur ou égal à a).
Soit a ∈ Z∗ . ∀b ∈ Z∗ , (b|a ⇒ |b| 6 |a|).
Soit a ∈ N∗ . Tout multiple strictement positif de a est supérieur ou égal à a.

Démonstration . Soit (a, b) ∈ (N∗ )2 . Si b divise a, alors il existe q ∈ N∗ tel que a = qb. On en déduit que

c Jean-Louis Rouget, 2018. Tous droits réservés. 2 http ://[Link]

 a = qb > 1 × b = b.
Si maintenant b est strictement négatif, alors b 6 0 < a et en particulier b 6 a.
Enfin, si (a, b) ∈ (Z∗ )2 , b est un diviseur de |a| et donc b 6 |a|. −b est aussi un diviseur de |a| et donc −b 6 a. Finalement, |b| 6 |a|.
❏

Théorème 4. ∀(a, b) ∈ Z∗ × Z, a|b ⇔ bZ ⊂ aZ.

Démonstration . Soit (a, b) ∈ Z∗ × Z.

• Supposons que a|b. Il existe q ∈ Z tel que b = qa. Soit alors k ∈ Z.

kb = kqa = (kq)a ∈ aZ.

Donc, bZ ⊂ aZ.
• Supposons que bZ ⊂ aZ. En particulier, puisque b = 1 × b ∈ bZ, on en déduit que b ∈ aZ et donc il existe q ∈ Z tel que b = aq.
Mais alors, a|b.
❏

Théorème 5.
1) Pour tout a ∈ Z∗ , a|0. Pour tout a ∈ Z, 0 est multiple de a.
2) Pour tout a ∈ Z, 1|a. Pour tout a ∈ Z, a est multiple de 1.
Démonstration .

1) Soit a ∈ Z∗ . 0Z = {0} ⊂ aZ et donc a divise 0 ou encore 0 est multiple de a. Cette dernière affirmation reste claire quand a = 0.
2) Soit a ∈ Z. aZ ⊂ Z = 1Z et donc 1|a ou encore a est multiple de 1.
❏

Théorème 6.
1) ∀a ∈ Z∗ , a|a (la relation de divisibilité dans Z∗ ou dans N∗ est réflexive).
2
2) a) ∀(a, b) ∈ (N∗ ) , (a|b et b|a) ⇔ a = b (la relation de divisibilité dans N∗ est anti-symétrique).
b) ∀(a, b) ∈ (Z∗ )2 , (a|b et b|a) ⇔ b = a ou b = −a.
3) ∀(a, b, c) ∈ Z∗ × Z∗ × Z, (a|b et b|c) ⇒ a|c (et en particulier, la relation de divisibilité dans Z∗ ou dans N∗ est
transitive).
La relation de divisibilité est une relation d’ordre sur N∗ et n’est pas une relation d’ordre sur Z∗ .

Théorème 7. Soit (a, b, c) ∈ Z × Z × Z∗ .

(c|a et c|b) ⇒ ∀(u, v) ∈ Z2 , c|(au + bv).

Démonstration . Soient (a, b, c) ∈ Z × Z × Z∗ . Soit (u, v) ∈ Z2 . Si c divise a et c divise b, alors il existe deux entiers relatifs
q et q ′ tels que a = qc et b = q ′ c. Mais alors au + bv = (uq + vq ′ ) c avec uq + vq ′ ∈ Z2 et donc c divise au + bv.
❏

c Jean-Louis Rouget, 2018. Tous droits réservés. 3 http ://[Link]

 Exercice 1. Trouver tous les entiers naturels n tels que 2n + 3 divise 3n + 7.
Solution 1. Soit n ∈ N tel que 2n + 3 divise 3n + 7. Alors, puisque 2n + 3 divise à la fois 2n + 3 et 3n + 7, 2n + 3 divise
encore 2(3n + 7) − 3(2n + 3) = 5. Puisque 2n + 3 est un entier naturel, on a donc nécessairement 2n + 3 = 1 ou 2n + 3 = 5
puis n = −1 ou n = 1 puis n = 1 car n est un entier naturel.
Réciproquement, si n = 1, alors 2n + 3 = 5 et 3n + 7 = 10 = 2 × 5. Donc, si n = 1, 2n + 3 divise effectivement 3n + 7.
Il existe un et un seul entier naturel n tel que 2n + 3 divise 3n + 7 à savoir n = 1.

2 Division euclidienne dans Z

On commence par le cas où on divise par un entier naturel non nul.
Théorème 8. Soit (a, b) ∈ Z × N∗ . Il existe un couple (q, r) d’entiers relatifs et un seul tels que

a = bq + r et 0 6 r < b.
q s’appelle le quotient de la division euclidienne de l’entier relatif a par l’entier naturel non nul b et r s’appelle le
reste de la division euclidienne de a par b.

➱ Commentaire .
⋄ La division euclidienne est la division où « on ne poursuit pas après la virgule ». Elle se présente dans les petites classes sous la
forme

50 13

11 3

De manière générale, elle s’écrit

a b

r q

a
⋄ Si x = est un rationnel non nul avec a ∈ Z∗ et b ∈ N∗ , la division euclidienne de a par b permet de décomposer x en somme
b
de sa partie entière et de sa partie décimale. Plus précisément, si a = bq + r abec 0 6 r < b (et q et r entiers relatifs), alors
a r
x= =q+
b b
r
où cette fois-ci 0 6 < 1. Par exemple
b
50 11
=3+ .
13 13

Théorème 9. Soit (a, b) ∈ Z × Z∗ . Il existe un couple (q, r) d’entiers relatifs et un seul tels que

a = bq + r et 0 6 r < |b|.

c Jean-Louis Rouget, 2018. Tous droits réservés. 4 http ://[Link]

 Sinon, un résultat évident mais qui doit être énoncé explicitement est :
Théorème 10. Soit (a, b) ∈ Z × Z∗ . b divise a si et seulement si le reste de la division euclidienne de a par b est nul.

Démonstration . Soit (a, b) ∈ Z × Z∗ . Si b divise a, il existe un entier relatif q tel que a = bq. Mais alors, a = bq + r avec
r = 0 ∈ J0, b − 1K. Le reste de la division euclidienne de b par a est donc 0.
Réciproquement, si le reste de la division euclidienne de b par a est nul, cette division euclidienne s’écrit a = bq où q est un entier
relatif et donc b divise a.
❏

Exercice 2. Pour n ∈ N∗ , on pose Mn = 2n − 1 (nombres de Mersenne). Effectuer la division euclidienne de Mp

par Mn pour n et p entiers naturels non nuls tels que p > n.
2
Solution 2. Soit (n, p) ∈ (N∗ ) tel que n < p. La division euclidienne de p par n s’écrit p = nq + r où q ∈ N∗ et
r ∈ J0, n − 1K.

Mp = 2p − 1 = 2qn+r − 1 = (2n )q × 2r − 1 = 2r (2n )q − 1 + (2r − 1)
 
2 q−1
= (2n − 1) 1 + 2n + (2n ) + . . . + (2n ) 2r + (2r − 1) (on rappelle que q ∈ N∗ )
= QMn + R
 
2 q−1
où Q = 1 + 2n + (2n ) + . . . + (2n ) 2r est un entier (car q ∈ N∗ ) et R = 2r − 1 = Mr est un entier. De plus,

0 6 r < n ⇒ 1 6 2r < 2n ⇒ 0 6 2r − 1 < 2n − 1 ⇒ 0 6 Mr < Mn .

 
2 q−1
Le quotient de la division euclidienne de Mp par Mn est 1 + 2n + (2n ) + . . . + (2n ) 2r et le reste est Mr où q et
r sont le quotient et le reste de la division euclidienne de p par n.

3 PGCD - PPCM
Dans tout ce qui suit, nous aurons besoin du résultat intuitif suivant que l’on admet et qui est une conséquence de l’axiome
de récurrence :
Théorème 11. Toute partie non vide de N admet un plus petit élément. Toute partie non vide et majorée de N admet
un plus grand élément.

3.1 PGCD
3.1.1 Définition du PGCD

Théorème 12. Soient a et b deux entiers relatifs tous deux non nuls. Il existe un entier naturel et un seul qui est un
diviseur commun à a et à b et qui est plus grand (au sens de la relation d’ordre usuelle 6) que tout diviseur commun
à a et à b dans Z.

Définition 2. Soient a et b deux entiers relatifs non nuls.

Le plus grand diviseur commun à a et à b se note PGCD(a, b) ou aussi a ∧ b.

2
Théorème 13. ∀(a, b) ∈ (Z∗ ) , a ∧ b = |a| ∧ |b|.

c Jean-Louis Rouget, 2018. Tous droits réservés. 6 http ://[Link]

3.1.2 L’algorithme d’Euclide
On commence par le « lemme d’Euclide » :

Théorème 14. Soient (a, b, q, r) ∈ Z4 tel que a 6= 0, b 6= 0, r 6= 0 et a = bq + r.

Alors a ∧ b = b ∧ r.

Nous allons maintenant utiliser ce résultat pour déterminer de manière algorithmique le PGCD de deux entiers. L’algo-
rithme ci-dessous s’appelle l’algorithme d’Euclide.
Commençons par un exemple. Déterminons le PGCD de a = 1386 et b = 270. La division euclidienne de a par b s’écrit

1386 = 5 × 270 + 36
et le théorème 14 nous permet alors d’affirmer que 1386 ∧ 270 = 270 ∧ 36. La division euclidienne de 270 par 36 s’écrit

270 = 7 × 36 + 18
et donc 1386 ∧ 270 = 270 ∧ 36 = 36 ∧ 18. Maintenant, puisque 36 = 2 × 18, 18 divise 36 et donc le plus grand diviseur
commun à 18 et 36 est 18. Finalement

1386 ∧ 270 = 270 ∧ 36 = 36 ∧ 18 = 18.

Passons au cas général. On se donne deux entiers naturels non nuls a et b tels que a < b. Posons r0 = a et r1 = b. On a
donc r1 < r0 .
• La division euclidienne de r0 = a par r1 = b s’écrit

r0 = r1 × q0 + r2 avec 0 6 r2 < r1 .
Si r2 = 0, r1 = b divise r0 = a. Le plus grand diviseur commun à a et b est donc r1 = b.
Sinon, 1 6 r2 < r1 et d’après le théorème 13, a ∧ b = r0 ∧ r1 = r1 ∧ r2 .
• On pose alors la division euclidienne de r1 par r2 qui s’écrit

r1 = r2 × q1 + r3 avec 0 6 r3 < r2 .
Si r3 = 0, r2 divise r1 et donc a ∧ b = r0 ∧ r1 = r1 ∧ r2 = r2 .
Sinon, 1 6 r3 < r2 et on pose la division euclidienne de r2 par r3 .
• De manière générale, pour k ∈ N tel que les restes r0 , . . . , rk+1 ne soient pas nuls, on pose la division euclidienne de
rk par rk+1 . Elle fournit un quotient qk ∈ N et un reste rk+2 ∈ N tels que

rk = rk+1 × qk + rk+2 avec 0 6 rk+2 < rk+1 .

On a alors a ∧ b = r1 ∧ r2 = . . . = rk ∧ rk+1 avec r0 > r1 > . . . > rk > rk+1 .
• S’il n’existe aucun reste nul, on obtient une suite de reste (rk )k∈N qui est une suite d’entiers naturels strictement
décroissante. Mais une telle suite n’existe pas car dans le cas contraire, pour tout k ∈ N, rk+1 6 rk − 1 puis, par
récurrence, pour tout k ∈ N, rk 6 r0 − k, ce qui entraine lim rk = −∞ et est absurde (puisque ∀k ∈ N, rk > 0).
k→+∞
Donc, il existe un reste qui est nul ou encore l’algorithme que l’on vient de mettre en place, s’arrête.
Soit rk0 +2 , k0 ∈ N, ce premier reste nul. On a rk0 = rk0 +1 × qk0 et donc rk0 +1 divise rk0 puis rk0 ∧ rk0 +1 = rk0 +1 .
Mais alors,

a ∧ b = r0 ∧ r1 = r1 ∧ r2 = . . . = rk0 ∧ rk0 +1 = rk0 +1 .

Ainsi, le PGCD de a et b est le dernier reste non nul dans l’algorithme d’Euclide. On peut énoncer :

c Jean-Louis Rouget, 2018. Tous droits réservés. 7 http ://[Link]

Théorème 15. Soient (a, b) ∈ (N∗ )2 tel que a > b. On pose r0 = a, r1 = b puis pour k ∈ N, tant que rk+1 6= 0, on
pose rk = qk rk+1 + rk+2 où (qk , rk+2 ) ∈ (N∗ )2 et 0 6 rk+2 < rk+1 .
• il existe un premier reste nul
• le PGCD de a et de b est le dernier reste non nul.

Exercice 3. Déterminer le PGCD de 273 et 455

Solution 3. Déterminons PGCD(455, 273) par l’algorithme d’Euclide.
455 = 1 × 273 + 182
273 = 1 × 182 + 91
182 = 2 × 91 + 0.
Le dernier reste non nul dans l’algorithme d’Euclide est 91 et donc

PGCD(455, 273) = 91.

Exercice 4. Pour n ∈ N∗ , on pose Mn = 2n − 1. Montrer que

2
∀(n, p) ∈ (N∗ ) , Mp ∧ Mp = Mn ∧ p .
2
Solution 4. Soit (n, p) ∈ (N∗ ) tel que n < p. La division euclidienne de p par n s’écrit p = nq + r où q et r sont deux
entiers naturels. D’après l’exercice no 2, la division euclidienne de Mp par Mn s’écrit

Mp = QMn + Mr (∗)
où Q est un entier naturel et 0 6 Mr < Mn . De plus,

Mr = 0 ⇔ 2r = 1 ⇔ r = 0 (∗∗).
Posons r0 = p, r1 = n puis pour k ∈ N, tant que rk+1 6= 0, posons rk = rk+1 qk + rk+2 où qk et rk sont des entiers
naturels tels que 0 6 rk+2 < rk+1 . Posons encore R0 = Mp , R1 = Mn puis pour k ∈ N, tant que Rk+1 6= 0, posons
Rk = Rk+1 Qk + Rk+2 où Qk et Rk sont des entiers naturels tels que 0 6 Rk+2 < Rk+1 .
(∗) et (∗∗) montrent que les deux algorithmes s’effectuent en parallèle : pour tout k ∈ N, tant que rk+1 6= 0, on a encore
Rk+1 6= 0 et Rk+2 = Mrk+2 .
Le dernier reste non nul dans l’algorithme d’Euclide appliqué à p et n est alors rk0 +1 = n ∧ p et le dernier reste non
nul dans l’algorithme d’Euclide appliqué à Mp et Mn est Rk0 +1 = Mrk0 +1 = Mn ∧ p .
Ceci montre que Mn ∧ Mp = Mn ∧ p .

A partir, de l’algorithme d’Euclide, on obtient une propriété importante du PGCD.

2
Théorème 16. Soit (a, b) ∈ (Z∗ ) .
Il existe (u, v) ∈ Z2 tel que a ∧ b = au + bv.

c Jean-Louis Rouget, 2018. Tous droits réservés. 8 http ://[Link]

3.1.3 Propriétés du PGCD

Théorème 17.
∀a ∈ N∗ , a ∧ a = a.
∀a ∈ Z∗ , a ∧ a = |a|.

Démonstration . Soit a ∈ N∗ . a est un diviseur commun à a et à a et tout diviseur commun à a et à a est inférieur ou égal
à a d’après le théorème 3. Donc, a ∧ a = a.
Si a ∈ Z∗ , a ∧ a = |a| ∧ |a| = |a|.
❏

Théorème 18. Soit (a, b) ∈ (Z∗ )2 . Les diviseurs communs à a et à b sont les diviseurs communs de leur PGCD.

Démonstration . Soit (a, b) ∈ (Z∗ )2 . a ∧ b est un diviseur commun à a et b. Par transitivité, un diviseur de a ∧ b est encore
un diviseur commun à a et b.
Réciproquement, posons d = a ∧ b ∈ N∗ . D’après le théorème 16, il existe deux entiers relatifs u et v tels que d = au + bv.
Soit alors d ′ un diviseur commun à a et b. d ′ divise au + bv d’après le théorème 7 ou encore d ′ divise d.
On a montré que les diviseurs communs à a et à b sont les diviseurs de a ∧ b.
❏

➱ Commentaire . Le résultat du théorème 18 s’écrit de manière plus condensée : div(a) ∩ div(b) = div(a ∧ b).

Théorème 19.
1) ∀(a, b) ∈ (N∗ )2 , a ∧ b = b ∧ a (commutativité du PGCD).
3
2) ∀(a, b, c) ∈ (N∗ ) , (a ∧ b) ∧ c = a ∧ (b ∧ c) (associativité du PGCD).
3) ∀a ∈ N∗ , a ∧ 1 = 1 (1 est absorbant).
 3
Théorème 20. ∀(a, b, c) ∈ (N∗ ) , (ca) ∧ (cb) = c(a ∧ b).

Ainsi, par exemple, 24 ∧ 36 = (2 × 12) ∧ (3 × 12) = 12(2 ∧ 3) = 12.

Une conséquence importante est le
2
Théorème 21. Soit (a, b) ∈ (N∗ ) . Soit d = a ∧ b. Il existe deux entiers naturels non nuls a ′ et b ′ tels que a = da ′
et b = db ′ et a ′ ∧ b ′ = 1.

Démonstration . d divise a et b. Donc, il existe deux entiers naturels non nuls a ′ et b ′ tels que a = da ′ et b = db ′ . De plus,

d = a ∧ b = (da ′ ) ∧ (db ′ ) = d(a ′ ∧ b ′ ).

Puisque d 6= 0, on obtient a ′ ∧ b ′ = 1 après simplification.
❏

3.2 PPCM
3.2.1 Définition du PPCM

Théorème 22. Soient a et b deux entiers relatifs tous deux non nuls. Il existe un entier naturel et un seul qui est un
multiple commun à a et à b et qui est plus petit (au sens de la relation d’ordre usuelle 6) que tout diviseur multiple
commun à a et à b dans N∗ .

Démonstration . Soit (a, b) ∈ (Z∗ )2 .

Existence. Soit E = {m ∈ N∗ / a|m et b|m}. E est une partie non vide de N car |ab| est un entier naturel non nul qui est un multiple
commun à a et à b et donc |ab| ∈ E.
E admet donc un plus petit élément qui est par définition un entier naturel non nul, multiple commun à a et à b et plus petit que
tout multiple commun à a et à b qui est strictement positif.
Unicité. Un multiple commun à a et à b et plus petit que tout multiple commun strictement positif à a et à b, est nécessairement
le minimum de E et on sait qu’un minimum est unique.
❏

Définition 3. Soient a et b deux entiers relatifs non nuls.

Le plus petit multiple commun à a et à b se note PPCM(a, b) ou aussi a ∨ b.
Par exemple, 4 ∨ 6 = 12 car les nombres 5, 6, . . . , 11 ne sont pas divisibles par 4 ou par 6 et 12 est divisible par 4 et par
6 (il faudra bien sûr améliorer les techniques de calcul d’un PPCM, ce qui se fera petit à petit).
On peut et on doit utiliser le PPCM pour réduire correctement au même dénominateur une somme de fractions. Par
exemple,
7 5 7×3 5×2 31
+ = + =
4 6 4×3 6×2 12
et non pas

c Jean-Louis Rouget, 2018. Tous droits réservés. 10 http ://[Link]

 7 5 42 20 62 31
+ = + = = .
4 6 24 24 24 12
Le meilleur dénominateur commun est bien 12 = 4 ∨ 6 et pas 24.

3.2.2 Propriétés du PPCM

On a immédiatement
Théorème 23.
1) ∀a ∈ N∗ , a ∨ a = a.
2) ∀a ∈ Z∗ , a ∨ a = |a|.
et aussi
2
Théorème 24. ∀(a, b) ∈ (Z∗ ) , a ∨ b = |a| ∨ |b|.

On a vu que les diviseurs communs à deux entiers relatifs non nuls sont les diviseurs de leur PGCD. De même,
2
Théorème 25. Soit (a, b) ∈ (Z∗ ) . Les multiples communs à a et à b sont les multiples de leur PPCM.

➱ Commentaire . Le résultat du théorème 25 peut être écrit de manière plus condensée : aZ ∩ bZ = (a ∨ b)Z.

Théorème 26.
2
1) ∀(a, b) ∈ (N∗ ) , a ∨ b = b ∨ a (commutativité du PPCM).
3
2) ∀(a, b, c) ∈ (N∗ ) , (a ∨ b) ∨ c = a ∨ (b ∨ c) (associativité du PPCM).
3) ∀a ∈ N∗ , 1 ∨ a = a (1 est élément neutre pour le PPCM dans N∗ ).

4 Nombres premiers entre eux. Théorèmes de Bézout et Gauss

4.1 Nombres premiers entre eux
2
Définition 4. Soit (a, b) ∈ (Z∗ ) . a et b sont premiers entre eux si et seulement si a ∧ b = 1.
Par exemple, 5 et 6 sont premiers entre eux car le seul diviseur commun strictement positif à 5 et à 6 est 1 et 4 et 6 ne
sont pas premiers entre eux car 4 ∧ 6 = 2 > 1.

c Jean-Louis Rouget, 2018. Tous droits réservés. 11 http ://[Link]

4.2 Théorème de Bézout

Théorème 28. (théorème de Bézout).

Soit (a, b) ∈ (Z∗ )2 .

a ∧ b = 1 ⇔ ∃(u, v) ∈ Z2 / au + bv = 1.
n
Plus généralement, soient n > 2 puis (a1 , . . . , an ) ∈ (Z∗ ) .
n
a1 ∧ . . . ∧ an = 1 ⇔ ∃ (u1 , . . . , un ) ∈ (Z∗ ) / a1 u1 + . . . + an un = 1.

Ainsi, par exemple, 21 et 10 sont premiers entre eux car 1 × 21 + (−2) × 10 = 1. Deux entiers consécutifs non nuls
n et n + 1 sont toujours premiers entre eux car 1 × (n + 1) + (−1) × n = 1. 6, 10 et 15 sont premiers entre eux car
1 × 6 + 1 × 10 + (−1) × 15 = 1.
Dans certaines situations, la question se pose de fournir explicitement des entiers u et v tels que au + bv = 1. L’algorithme
d’Euclide fournit un procédé d’obtention d’un tel couple comme le montre l’exercice suivant :
Exercice 6. Déterminer deux entiers relatifs u et v tels que 337u + 241v = 1.
Solution 6. L’algorithme d’Euclide appliqué à 337 et 241 s’écrit
337 = 1 × 241 + 96
241 = 2 × 96 + 49
96 = 1 × 49 + 47
49 = 1 × 47 + 2
47 = 23 × 2 + 1
2 = 2 × 1 + 0.
Le dernier reste non nul dans l’algorithme d’Euclide est 1 et donc 337 ∧ 241 = 1. D’après le théorème de Bézout, il
existe deux entiers relatifs u et v tels que 337u + 241v = 1. Déterminons explicitement un tel couple. En remontant dans
l’algorithme d’Euclide, on obtient

1 = 47 − 23 × 2
= 47 − 23(49 − 1 × 47) = −23 × 49 + 24 × 47
= −23 × 49 + 24(96 − 1 × 49) = 24 × 96 − 47 × 49
= 24 × 96 − 47(241 − 2 × 96) = −47 × 241 + 118 × 96
= −47 × 241 + 118(337 − 1 × 241) = 118 × 337 − 165 × 241.

Le couple (u, v) = (118, −165) est un couple d’entiers relatifs vérifiant 337u + 241v = 1.

4.3 Lemme de Gauss

Théorème 29. (lemme de Gauss).

Soient a, b et c trois entiers relatifs tels que a 6= 0 et b 6= 0.
Si a divise bc et si a et b sont premiers entre eux, alors a divise c.

c Jean-Louis Rouget, 2018. Tous droits réservés. 13 http ://[Link]

Démonstration . Soient a, b et c trois entiers relatifs tels que a 6= 0 et b 6= 0 et a divise bc et a et b sont premiers entre eux.
Il existe q ∈ Z tels que bc = qa et d’autre part, d’après le théorème de Bézout, il existe deux entiers relatifs u et v tels que
au + bv = 1.
On multiplie les deux membres de cette dernière égalité par c et on obtient

c = acu + bcv = acu + qav = a(cu + qv)

où cu + qv est un entier relatif. Donc, a divise c.
❏

Il ne faut pas croire que si un entier a divise un produit bc, a divise automatiquement l’un des deux entiers b ou c. Par
exemple, 8 divise 24 = 4 × 6 mais 8 ne divise ni 4, ni 6. Le théorème de Gauss dit que si de plus, a est premier avec un
des deux entiers, alors a divise l’autre entier. Par exemple, 4 divise 24 = 3 × 8 et 4 est premier à 3 et de fait, 4 divise 8.

4.4 Quelques conséquences des théorèmes de Bézout et Gauss

Théorème 30. Soit (a, b) ∈ (N∗ )2 . On pose m = a ∨ b et d = a ∧ b. Alors,

md = ab.

Démonstration . Soit (a, b) ∈ (N∗ )2 . D’après le théorème 21, il existe deux entiers naturels non nuls a ′ et b ′ tels que a = da ′ ,
b = db ′ et a ′ ∧ b ′ = 1. On a alors

ab = d(da ′ b ′ ) (∗).
Montrons que m = da b . da b = ab = a b et donc da ′ b ′ est un commun à a et à b. D’après le théorème 25, da ′ b ′ est un
′ ′ ′ ′ ′ ′

multiple de m ou encore m divise da ′ b ′ .

Inversement, m est un multiple de a et b. Posons donc m = ka = lb où (k, l) ∈ (N∗ )2 . Puisque ka = lb, on a encore kda ′ = ldb ′
puis ka ′ = lb ′ . b ′ divise lb ′ = ka ′ et b ′ est premier à a ′ . D’après le théorème de Gauss, b ′ divise k. On peut donc poser k = k ′ b ′
où k ′ ∈ N∗ . On obtient m = ka = k ′ da ′ b ′ et donc da ′ b ′ divise m.
En résumé, m divise da ′ b ′ et da ′ b ′ divise m. Puisque m et da ′ b ′ sont des entiers naturels non nuls, on en déduit que m = da ′ b ′ .
L’égalité (∗) s’écrit alors ab = md.
❏

Dans la démonstration précédente, on a obtenu plusieurs procédés équivalents pour calculer le PPCM de deux entiers
quand on connaît leur PGCD. Prenons par exemple a = 24 = 2 × 12 et b = 36 = 3 × 12. Puisque 2 ∧ 3 = 1, on a d = 12,
ab 24 × 36
a ′ = 2 et b ′ = 3. On en déduit que m = da ′ b ′ = 12 × 2 × 3 = 72 ou bien directement m = = = 72.
d 12
Théorème 31. Soient n > 2 puis (a, b1 , . . . , bn )!∈ (Z∗ )n+1 .
Y n
(Pour tout i ∈ J1, nK, a ∧ bi = 1) ⇔ a ∧ bi = 1.
i=1

c Jean-Louis Rouget, 2018. Tous droits réservés. 14 http ://[Link]

Théorème 32. Soit (a, b) ∈ (Z∗ )2 . a ∧ b = 1 ⇔ ∀(n, m) ∈ N2 , an ∧ bm = 1.

Théorème 33. Soient n > 2 puis (a, b1 , . . . , bn ) ∈ (Z∗ )n+1 .

n
Y
Si pour tout i ∈ J1, nK, bi divise a et si les bi , 1 6 i 6 n, sont deux à deux premiers entre eux, alors bi divise a.
i=1

Démonstration . Montrons le résultat par récurrence.

• Soient a, b1 et b2 trois entiers relatifs non nuls tels que b1 et b2 divisent a et b1 ∧ b2 = 1.
Il existe k ∈ Z tel que a = kb1 . b2 divise a = kb1 et b2 ∧ b1 = 1. D’après le théorème de Gauss, b2 divise k. Donc, il existe
k ′ ∈ Z tel que k = k ′ b2 puis a = k ′ b1 b2 . Ceci montre que b1 b2 divise a.
• Soit n > 2. Supposons le résultat pour n. Soient a, b1 , . . . , bn+1 , n + 2 entiers relatifs non nuls tels que pour tout i ∈ J1, n + 1K,
bi divise a et b1 , . . . , bn+1 sont deux à deux premiers entre eux.
n
Y n
Y
Par hypothèse de récurrence, bi divise a. D’après le théorème 31, bi et bn+1 sont premiers entre eux. D’après le cas
i=1 i=1
n+1
Y
n = 2, bi divise a.
i=1

Le résultat est démontré par récurrence.

❏

Une autre application des théorèmes de Bézout et Gauss est la forme irréductible d’un nombre rationnel :
2 a
Théorème 34. Pour tout rationnel strictement positif r, il existe un couple (a, b) ∈ (N∗ ) et un seul tel que r =
b
et a ∧ b = 1.

Démonstration .
p
Existence. Soit r ∈ Q+∗ . Il existe deux entiers naturels non nuls p et q tels que r = . On sait que l’on peut écrire p = da et
q
q = db où d = p ∧ q et a et b sont deux entiers naturels non nuls premiers entre eux. On a alors

p da a
r= = =
q db b
où cette fois-ci a et b sont premiers entre eux.
a1 a2
Unicité. Soit (a1 , a2 , b1 , b2 ) ∈ (N∗ )4 tel que a1 ∧ b1 = 1, a2 ∧ b2 = 1 et
= . Alors, a1 b2 = a2 b1 . a2 divise a2 b1 = a1 b2 et
b1 b2
a2 ∧ b2 = 1. Donc, a2 divise a1 d’après le théorème de Gauss. De même, a1 divise a2 et finalement a1 = a2 puis b1 = b2 .
❏

a
Définition 6. L’écriture d’un rationnel strictement positif r sous la forme r = avec a ∧ b = 1 s’appelle la forme
b
irréductible du rationnel r.

4.5 Résolution dans Z2 de l’équation ax + by = c

On se donne trois entiers relatifs a, b et c tels que a 6= 0 et b 6= 0. On veut résoudre dans Z2 l’équation

ax + by = c (E),
d’inconnue (x, y) ∈ Z2 .
• Posons d = a ∧ b. Pour tout couple d’entiers relatifs (x, y), d divise ax + by. Si de plus ax + by = c, alors d doit
diviser c. Donc, si d ne divise pas c, l’équation (E) n’a pas de solution dans Z2 . C’est par exemple le cas de l’équation
2x + 4y = 3 : 2x + 4y est toujours un nombre relatif pair, alors que 3 est un nombre impair. Cette équation n’a pas de
solution dans Z2 .
Supposons maintenant que d divise c. On peut écrire a = da ′ , b = db ′ et c = dc ′ où a ′ et b ′ dont deux entiers relatifs
premiers entre eux et c ′ est un entier relatif. Après simplification par d, l’équation (E) s’écrit

a ′x + b ′y = c ′,

c Jean-Louis Rouget, 2018. Tous droits réservés. 15 http ://[Link]

où cette fois-ci a ′ et b ′ sont premiers entre eux.
• Soit donc a et b deux entiers relatifs non nuls et premiers entre eux. Soit (E0 ) l’équation

ax + by = 1.
D’après le théorème de Bézout, il existe au moins une solution (x0′ , y0′ ) de cette équation dans Z2 . On rappelle qu’une
telle solution peut par exemple être obtenue à partir de l’algorithme d’Euclide.
Par définition, ax0′ + by0′ = 1. En multipliant les deux membres de cette égalité par c, on obtient a (cx0′ ) + b (xy0′ ) = c.
Le couple (x0 , y0 ) = (cx0′ , cy0′ ) est une solution particulière dans Z2 de l’équation (E).
Par exemple, le couple (x0′ , y0′ ) = (−1, 2) est une solution particulière de l’équation 7x + 4y = 1 et donc le couple
(x0 , y0 ) = (−3, 6) est une solution particulière de l’équation 7x + 4y = 3.
On a ainsi montré que quand a ∧ b = 1, pour tout c ∈ Z, l’équation ax + by = c admet toujours au moins une solution
(x0 , y0 ) dans Z2 .
2
• On peut maintenant résoudre complètement l’équation (E). Soit (a, b) ∈ (Z∗ ) tel que a ∧ b = 1. Soient c ∈ Z puis
(x0 , y0 ) une solution particulière dans Z2 de l’équation (E) : ax + by = c.
Soit (x, y) ∈ Z2 .

(x, y) solution de (E) ⇔ ax + by = c ⇔ ax + by = ax0 + by0

⇔ a (x0 − x) = b (y − y0 ) .

Si (x, y) est solution de (E), nécessairement b divise b (y − y0 ) = a (x0 − x). Puisque a ∧ b = 1, le théorème de Gauss
permet d’affirmer que b divise x0 − x et donc il existe k ∈ Z tel que x0 − x = kb ou encore x = x0 − kb. De même, a divise
y − y0 et donc il existe k ′ ∈ Z2 tel que y − y0 = k ′ a ou encore y = y0 + k ′ a.
Réciproquement, soient (k, k ′ ) ∈ Z2 puis (x, y) = (x0 − kb, y0 + k ′ a).

(x, y) solution de (E) ⇔ a (x0 − x) = b (y − y0 ) ⇔ a(kb) = b(k ′ a)

⇔ (k − k ′ )ab = 0
⇔ k = k ′ (car ab 6= 0).

Les solutions de (E) dans Z2 sont les couples de la forme (x0 − kb, y0 + ka), k ∈ Z. On peut résumer tout ce qui précède
dans un théorème :
Théorème 35.
1) Soient a, b et c trois entiers relatifs tels que a 6= 0, b 6= 0. L’équation (E) : ax + by = c admet au moins une
solution dans Z2 si et seulement si a ∧ b divise c. Dans ce cas, quite à diviser les deux membres de (E) par a ∧ b, on
se ramène à la situation où a ∧ b = 1.
2) Soient a, b et c trois entiers relatifs tels que a 6= 0, b 6= 0 et a ∧ b = 1. Les solutions de (E) dans Z2 sont les couples
de la forme

(x, y) = (x0 − kb, y0 + ka) , k ∈ Z

où (x0 , y0 ) est une solution particulière de (E) dans Z2 .

Exercice 7. Résoudre dans Z2 l’équation (E) : 12x + 7y = 2.

Solution 1. L’algorithme d’Euclide appliqué à 7 et 12 s’écrit
12 = 1 × 7 + 5
7=1×5+2
5=2×2+1
(En particulier, 7 ∧ 12 = 1). Donc,

1=5−2×2
= 5 − 2(7 − 1 × 5) = 3 × 5 − 2 × 7
= 3(12 − 1 × 7) − 2 × 7 = 3 × 12 − 5 × 7.

c Jean-Louis Rouget, 2018. Tous droits réservés. 16 http ://[Link]

En multipliant les deux membres de l’égalité par 2, on obtient 6 × 12 − 10 × 7 = 2. Le couple (x0 , y0 ) = (6, −10) est une
solution particulière de (E) dans Z2 .
Soit (x, y) ∈ Z2 .

(x, y) solution de (E) ⇔ 12x + 7y = 2 ⇔ 12x + 7y = 12x0 + 7y0

⇔ 12 (x − x0 ) = 7 (y0 − y) .

Si (x, y) est solution de (E), nécessairement 7 divise 7 (y0 − y) = 12 (x − x0 ). Puisque 7 ∧ 12 = 1, le théorème de Gauss
permet d’affirmer que 7 divise x − x0 et donc il existe k ∈ Z tel que x − x0 = 7k ou encore x = x0 + 7k. De même, 12
divise y0 − y et donc il existe k ′ ∈ Z2 tel que y0 − y = 12k ′ ou encore y = y0 − 12k ′ .
Réciproquement, soient (k, k ′ ) ∈ Z2 puis (x, y) = (x0 + 7k, y0 − 12k ′ ).

(x, y) solution de (E) ⇔ 12 (x − x0 ) = 7 (y0 − y) ⇔ 12 × 7 × k = 7 × 12 × k ′

⇔ k = k ′.

Les solutions de (E) : 12x + 7y = 2 dans Z2 sont les couples de la forme (6 + 7k, −10 − 12k), k ∈ Z.

La résolution dans Z2 de l’équation ax + by = c a bien sûr une interprétation géométrique. Si le plan est rapporté à un
repère R, l’ensemble D des points M du plan de coordonnées (x, y) ∈ R2 est une droite. Résoudre dans Z2 l’équation
ax + by = c, c’est déterminer les points de cette droite à coordonnées entières.
Par exemple, les points à coordonnées entières de la droite d’équation 2x + 3y = 1 sont les points de coordonnées
(−1 − 3k, 1 + 2k). Ces coordonnées peuvent se lire sous la forme (−1, 1) + k(−3, 2), k ∈ Z. Le vecteur − →
u de coordonnées
(−3, 2) est un vecteur directeur directeur particulier de cette droite à coordonnées entières et le point A de coordonnées
(−1, 1) est un point particulier de cette droite à coordonnées entières. Les points solutions s’écrivent alors A + k−
→
u , k ∈ Z.

b
3
−
→
u
2

b
1
A

−4 −3 −2 −1 1 2 3 4 5
−1 b

−2

−3 b

5 Nombres premiers. Décomposition primaire

5.1 Définition des nombres premiers

Définition 7. Soit n un entier naturel supérieur ou égal à 2.

n est premier si et seulement si n admet exactement deux diviseurs strictement positifs, à savoir 1 et lui-même. On
note P l’ensemble des nombres premiers.
Un entier supérieur ou égal à 2 non premier est dit composé.

⋄ Les premiers nombres premiers sont

2 3 5 7 11 13 17 19 ...

c Jean-Louis Rouget, 2018. Tous droits réservés. 17 http ://[Link]

Théorème 36. Soient n un entier naturel supérieur ou égal à 2.
2
n est composé si et seulement si il existe (a, b) ∈ (N∗ ) tel que 1 < a < n, 1 < b < n et n = ab.
2
n est premier si et seulement si pour tout (a, b) ∈ (N∗ ) , (n = ab ⇒ a = 1 ou b = 1).

5.2 Quelques propriétés des nombres premiers

Théorème 37. Soient n un entier naturel supérieur ou égal à 2 et p un nombre premier.
Si p divise n, alors n ∧ p = p et si p ne divise pas n, alors n ∧ p = 1.

Théorème 38. Deux nombres premiers distincts sont premiers entre eux.
Plus généralement, si p et q sont des nombres premiers distincts, alors pour tout (α, β) ∈ N2 , pα ∧ qβ = 1.

Théorème 39. Tout nombre entier n > 2 admet au moins un diviseur qui est un nombre premier.

Théorème 40. Soient p un nombre premier et a1 , . . . , an , n entiers naturels non nuls, n > 2. Si p divise a1 × . . .× an
alors p divise l’un des ai , 1 6 i 6 n.

5.3 Le théorème fondamental de l’arithmétique

Théorème 41. (théorème fondamental de l’arithmétique)
Tout entier naturel supérieur ou égal à 2 se décompose de manière unique, à l’ordre près des facteurs, en produit de
facteurs premiers.

Par exemple,

792 792 = 2 × 396 396 = 22 × 198 198 = 23 × 99 099

= 23 × 3 × 33 033 = 22 × 32 × 11 011
= 22 × 32 × 7 × 1573
= 22 × 32 × 7 × 11 × 143 = 22 × 32 × 7 × 112 × 13.

Théorème 44. Soient a et b deux entiers supérieurs ou égaux à 2.

a et b sont premiers entre eux si et seulement si a et b n’ont pas de facteur premier commun.

c Jean-Louis Rouget, 2018. Tous droits réservés. 18 http ://[Link]

Théorème 45. Soit n un entier supérieur ou égal à 2. On suppose que la décomposition primaire de n s’écrit

n = pα αk
1 × . . . × pk .
1

1 × . . . × pk où, pour tout i ∈ J1, kK, 0 6 βi 6 αi .

Les diviseurs de n sont les entiers de la forme pβ1 βk

Yk
Le nombre des diviseurs de n est (αi + 1).
i=1

Par exemple, puisque 72 = 23 × 32 , 72 admet (3 + 1)(2 + 1) = 12 diviseurs. Les diviseurs de 72 sont les nombres

20 × 30 = 1 21 × 30 = 2 22 × 30 = 4 23 × 30 = 8
20 × 31 = 3 21 × 31 = 6 22 × 31 = 12 23 × 31 = 24
20 × 32 = 9 21 × 32 = 18 22 × 32 = 36 23 × 32 = 72

Théorème 45. Soient a et b deux entiers naturels non nuls.

β1 βk
On suppose que a = pα αk
1 × . . . × pk et b = p1 × . . . × pk où k ∈ N , p1 , . . . , pk , sont des nombres premiers deux
1 ∗

à deux distincts et α1 , . . . , αk , β1 , . . . , βk , sont des entiers naturels.

Min(α1 ,β1 ) Min(αk ,βk ) Max(α1 ,β1 ) Max(αk ,βk )
Alors, a ∧ b = p1 × . . . × pk et a ∨ b = p1 × . . . × pk .

Exemple. 120 = 23 × 31 × 50 × 71 et 252 = 22 × 32 × 50 × 71 . Donc 120 ∧ 252 = 22 × 31 × 50 × 70 = 12 et 120 ∨ 252 =

23 × 32 × 51 × 71 = 2520.

➱ Commentaire . Pour tout (α, β) ∈ N2 , Min(α, β) + Max(α, β) = α + β et donc, on retrouve l’égalité

k
! k
! k k
Y Min(αi ,βi )
Y Max(αi ,βi )
Y Min(αi ,βi )+Max(αi ,βi )
Y α +βi
(a ∧ b)(a ∨ b) = pi pi = pi = pi i = ab.
i=1 i=1 i=1 i=1

c Jean-Louis Rouget, 2018. Tous droits réservés. 25 http ://[Link]

6 Congruences
6.1 Définition
Définition 10. Soit n un entier naturel. Soient a et b deux entiers relatifs.
b est congru à a modulo n si et seulement si b − a est un multiple de n ou encore si et seulement si il existe q ∈ Z
tel que b = a + qn.
La phrase « b est congru à a modulo n » se note a ≡ b [n] ou aussi a ≡ b (mod n).
Remarques.
• a ≡ b [0] ⇔ ∃q ∈ Z/ b = a + q × 0 ⇔ a = b. La congruence modulo 0 est donc tout simplement l’égalité.
• a ≡ b [1] ⇔ b − a multiple de 1 ⇔ b − a ∈ Z. Cette dernière phrase est toujours vraie et donc tout entier est congru à
tout entier modulo 1.
• a ≡ 0 [2] signifie que a est pair et a ≡ 1 [2] signifie que a est impair. Plus généralement, a ≡ b [2] ⇔ b − a multiple de
2. Ceci équivaut à dire que les entiers a et b ont même parité (ils sont tous les deux pairs ou tous les deux impairs).
• Les entiers relatifs a vérifiant a ≡ 0 [n] sont les multiples de n : {a ∈ Z/ a ≡ 0 [n]} = nZ. ❏
Exemples.
Puisque 24 = 9 + 3 × 5, on a encore 24 − 9 ∈ 5Z et donc 9 ≡ 24 [5]. La congruence modulo 5 a pour effet d’« effacer tout
multiple de 5 ».
Puisque −3 = 11 − 2 × 7, on a 11 ≡ −3 [7]. ❏
Un résultat immédiat est :
Théorème 46. Soit n un entier naturel non nul. Soit a un entier relatif. Soit r le reste de la division euclidienne de
a par n. Alors, a ≡ r [n]

Une des premières propriétés de la congruence modulo n est qu’elle se comporte comme l’égalité. Plus précisément,
Théorème 47. Soit n un entier naturel.
La congruence modulo n est une relation d’équivalence.

6.2 Calculs avec des congruences

Nous allons maintenant apprendre à calculer avec des congruences.

Théorème 48. (compatibilité avec l’addition). Soit n un entier naturel.
1) ∀(a, b, c) ∈ Z3 , (a ≡ b [n] ⇒ a + c ≡ b + c [n]).
2) ∀(a, b, c, d) ∈ Z4 , (a ≡ b [n] et c ≡ d [n] ⇒ a + c ≡ b + d [n]).

Ainsi, on peut additionner membre à membre des congruences.

Théorème 49. (compatibilité avec la multiplication). Soit n un entier naturel.
1) ∀(a, b, c) ∈ Z3 , (a ≡ b [n] ⇒ ac ≡ bc [n]).
2) ∀(a, b, c, d) ∈ Z4 , (a ≡ b [n] et c ≡ d [n] ⇒ ac ≡ bd [n]).
3) ∀(a, b) ∈ Z2 , ∀k ∈ N, (a ≡ b [n] ⇒ ak ≡ bk [n]).
 Théorème 50. (simplifications). Soit n un entier naturel non nul.
1) ∀(a, b, c) ∈ Z3 , a + c ≡ b + c [n] ⇒ a ≡ b [n] (tout entier relatif est simplifiable pour l’addition).
2) a) ∀(a, b) ∈ Z2 , ∀c ∈ Z∗ , (ac ≡ bc [n] et c ∧ n = 1) ⇒ a ≡ b [n].
b) Si n > 2, les entiers relatifs simplifiables modulo n sont les entiers non nuls et premiers à n.

En résumé, si n > 2, pour tout (a, b, c) ∈ Z3 , a + c ≡ b + c [n] ⇔ a ≡ b [n] et pour tout (a, b) ∈ Z2 , si c est un entier
relatif non nul premier à n, ac ≡ bc [n] ⇔ a ≡ b [n]. Ces résultats sont essentiels pour résoudre des congruences :
Exercice 9. Résoudre dans Z les congruences :
1) 3x + 5 ≡ 4 [7].
2) a) 6x + 5 ≡ 2 [9].
b) 6x + 5 ≡ 1 [9].
Solution 9. Dans les deux questions, on note S l’ensemble des solutions de la congruence proposée.
1) Soit x ∈ Z.

3x + 5 ≡ 4 [7] ⇔ 3x + 5 + (−5) ≡ 4 + (−5) [7] ⇔ 3x ≡ −1 [7].

Maintenant, 3 × 5 = 15 ≡ 1 [7]. Donc, 3x ≡ −1 [7] ⇒ 5 × 3x ≡ 5(−1) [7] ⇒ x ≡ −5 [7] et x ≡ −5 [7] ⇒ 3x ≡ −15 [7] ⇒
3x ≡ −1 [7]. Donc,

3x + 5 ≡ 4 [7] ⇔ x ≡ −5 [7] ⇔ x ≡ 2 [7].

Ainsi, S = {2 + 7k, k ∈ Z} = 2 + 7Z.
2) a) Soit x ∈ Z.

6x + 5 ≡ 2 [9] ⇔ 6x = −3 [9] ⇔ ∃k ∈ Z/ 6x = −3 + 9k ⇔ ∃k ∈ Z/ 2x = −1 + 3k
⇔ 2x ≡ −1 [3] ⇔ 2 × 2x ≡ 2 × (−1) [3] (car 2 ∧ 3 = 1)
⇔ x ≡ −2 [3] ⇔ x ≡ 1 [3].

Ainsi, S = {1 + 3k, k ∈ Z} = 1 + 3Z.

b) Soit x ∈ Z.

6x + 5 ≡ 1 [9] ⇔ 6x = −4 [9] ⇔ ∃k ∈ Z/ 6x − 9k = −4.

Maintenant, l’équation 6x = −4 + 9k n’a pas de solution dans Z car 6x − 9k est un entier divisible par 3 alors que −4 n’est
un entier divisible par 3. Ainsi, S = ∅.

Exercice 10. Résoudre dans Z2 le système de congruence

3x − 2y ≡ 1 [7]
4x + 5y ≡ 3 [7]

Solution 10. On note S l’ensemble des solutions du sytème proposé. Soit (x, y) ∈ Z2 .

c Jean-Louis Rouget, 2018. Tous droits réservés. 28 http ://[Link]

 3x − 2y ≡ 1 [7] 3x ≡ 1 + 2y [7] 5 × 3x ≡ 5(1 + 2y) [7]
⇔ ⇔ (car 5 ∧ 7 = 1)
4x + 5y ≡ 3 [7] 4x + 5y ≡ 3 [7] 4x + 5y ≡ 3 [7]
x ≡ 5 + 10y [7] x ≡ −2 + 3y [7]
⇔ ⇔
4x + 5y ≡ 3 [7] 4(−2 + 3y) + 5y ≡ 3 [7]
x ≡ −2 + 3y [7] 3y ≡ −3 [7] y ≡ −1 [7]
⇔ ⇔ ⇔ (car 3 ∧ 7 = 1)
17y ≡ 11 [7] x ≡ −2 + 3y [7] x ≡ −2 + 3(−1) [7]
y ≡ −1 [7] y ≡ −1 [7]
⇔ ⇔ .
x ≡ −5 [7] x ≡ 2 [7]

Donc, S = (2 + 7k, −1 + 7k ′ ), (k, k ′ ) ∈ Z2 = (2 + 7Z) × (−1 + 7Z).

6.3 Le petit théorème de Fermat

Théorème 51. (petit théorème de Fermat). Soit p un nombre premier.

1) Pour tout a ∈ N, ap ≡ a [p].
2) Pour tout a ∈ N∗ , (a ∧ p = 1 ⇒ ap−1 ≡ 1 [p]).