Séquence 3 : Arithmétique dans Z

1 Divisibilité et division euclidienne

Définition 1. Soient a, b ∈ Z. On dit que b divise a et on note b|a s’il existe q ∈ Z
tel que a = bq.
Remarque 1.

• La relation de divisibilité est une relation de préordre dans Z, c’est-à-dire

qu’elle est reflexive et transitive, mais elle n’est pas antisymétrique.
• ∀a ∈ Z on a a|0 et aussi 1|a.
• Si a|1 alors a = +1 ou a = −1.
• (a|b et b|a) =⇒ b = ±a
• (a|b et b|c) =⇒ a|c
• (a|b et a|c) =⇒ a|b + c
Théorème 1 (Division euclidienne). Soit a ∈ Z et b ∈ N \ {0}. Il existe des
entiers q, r ∈ Z tels que a = bq + r et 0 ≤ r < b. De plus q et r sont uniques et
sont respectivement appelés quotient et reste. On dit que a est le dividende et b le
diviseur.
Nous avons donc l’équivalence : r = 0 si et seulement si b divise a.
Preuve. 
Existence. On peut supposer a ≥ 0 pour simplifier. Soit N = n ∈ N | bn ≤
a . C’est un ensemble non vide car n = 0 ∈ N . De plus pour n ∈ N , on a n ≤ a.
Il y a donc un nombre fini d’éléments dans N , notons q = max N le plus grand
élément.
Alors qb ≤ a car q ∈ N , et (q + 1)b > a car q + 1 ∈
/ N , donc

qb ≤ a < (q + 1)b = qb + b.

On définit alors r = a − qb, r vérifie alors 0 ≤ r = a − qb < b.

Unicité. Supposons que q 0 , r0 soient deux entiers qui vérifient les conditions du
théorème. Tout d’abord a = bq + r = bq 0 + r0 et donc b(q − q 0 ) = r0 − r. D’autre

BP :64 Ouagadougou cité AN II Burkina Faso 1 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
part 0 ≤ r0 < b et 0 ≤ r < b donc −b < r0 − r < b. Mais r0 − r = b(q − q 0 ) donc on
obtient −b < b(q − q 0 ) < b. On peut diviser par b > 0 pour avoir −1 < q − q 0 < 1.
Comme q − q 0 est un entier, la seule possibilité est q − q 0 = 0 et donc q = q 0 .
Repartant de r0 − r = b(q − q 0 ) on obtient maintenant r = r0 .

2 Algorithme d’Euclide
Soient a, b ∈ Z, on appelle diviseur commun de a et b tout entier relatif qui est
à la fois diviseur de a et de b ; on appelle multiple commun de a et b tout entier
relatif divisible à la fois par a et b ;

Définition 2. Soient a, b ∈ Z deux entiers, non tous les deux nuls. Le plus grand
entier qui divise à la fois a et b s’appelle le plus grand diviseur commun de a, b et
se note pgcd(a, b) ou a ∧ b.

Remarque 2.

• pgcd(a, ka) = a, pour tout k ∈ Z et a ≥ 0.

• ∀a ≥ 0 : pgcd(a, 0) = a et pgcd(a, 1) = 1.

Lemme 1. Soient a, b ∈ N∗ . Écrivons la division euclidienne a = bq + r. Alors

pgcd(a, b) = pgcd(b, r)

Preuve. Soit d un diviseur de a et de b. Alors d divise b donc aussi bq, en

plus d divise a donc d divise a − bq = r. Réciproquement soit d un diviseur de b et
de r. Alors d divise aussi bq + r = a.
Ainsi les diviseurs de a et de b sont exactement les mêmes que les diviseurs de b
et r ; d’où le résultat.

Algorithme d’Euclide.
On souhaite calculer le pgcd de a, b ∈ N∗ . On peut supposer a ≥ b. On calcule
des divisions euclidiennes successives. Le pgcd sera le dernier reste non nul.
∗ division de a par b, a = bq1 + r1 . Par le lemme précédent pgcd(a, b) =
pgcd(b, r1 ) et si r1 = 0 alors pgcd(a, b) = b sinon on continue :
∗ b = r1 q2 + r2 , pgcd(a, b) = pgcd(b, r1 ) = pgcd(r1 , r2 ),
∗ r1 = r2 q3 + r3 , pgcd(a, b) = pgcd(r2 , r3 ),
∗ ...
∗ rk−2 = rk−1 qk + rk , pgcd(a, b) = pgcd(rk−1 , rk ),
∗ rk−1 = rk qk + 0. pgcd(a, b) = pgcd(rk , 0) = rk .

BP :64 Ouagadougou cité AN II Burkina Faso 2 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
 Comme à chaque étape le reste est plus petit que le quotient on sait que 0 ≤
ri+1 < ri . Ainsi l’algorithme se termine car nous sommes sûrs d’obtenir un reste
nul, les restes formant une suite décroissante d’entiers positifs ou nuls : b > r1 >
r2 > · · · ≥ 0.

Exemple 1. Calculons le pgcd de a = 560 et b = 133.

560 = 133 × 4 + 28
133 = 28 × 4 + 21
28 = 21 × 1 + 7
21 = 7 × 3 + 0
Ainsi pgcd(560, 133) = 7.

Exemple 2. Calculons pgcd(1599, 3471).

3471 = 1599 × 2 + 273

1599 = 273 × 5 + 234
273 = 234 × 1 + 39
234 = 39 × 6 + 0

Ainsi pgcd(3471, 1599) = 39.

Définition 3. Deux entiers a, b sont premiers entre eux si pgcd(a, b) = 1.

Exemple 3. Pour tout a ∈ Z, a et a + 1 sont premiers entre eux. En effet soit d

un diviseur commun à a et à a + 1. Alors d divise aussi a + 1 − a. Donc d divise
1 mais alors d = −1 ou d = +1. Le plus grand diviseur de a et a + 1 est donc 1.
Et donc pgcd(a, a + 1) = 1.

Si deux entiers ne sont pas premiers entre eux, on peut s’y ramener en divisant
par leur pgcd :

Exemple 4. Pour deux entiers quelconques  a, b ∈0 Z, notons d = pgcd(a, b). La dé-

a = ad
composition suivante est souvent utile : avec a0 , b0 ∈ Z et pgcd(a0 , b0 ) = 1
b = b0 d

Définition 4. Le ppcm(a, b) (plus petit multiple commun) est le plus petit entier
positif divisible par a et par b.

Le pgcd et le ppcm sont liés par la formule suivante :

Proposition 1. Si a, b sont des entiers (non tous les deux nuls) alors

pgcd(a, b) × ppcm(a, b) = |ab|

BP :64 Ouagadougou cité AN II Burkina Faso 3 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
 |ab|
Preuve. On pose d = pgcd(a, b) et m = pgcd(a,b) . Pour simplifier on suppose
a > 0 et b > 0. On écrit a = da et b = db . Alors ab = d2 a0 b0 et donc m = da0 b0 .
0 0

Ainsi m = ab0 = a0 b est un multiple de a et de b.

Il reste à montrer que c’est le plus petit multiple. Si n est un autre multiple de
a et de b alors n = ka = lb donc kda0 = ldb0 et ka0 = lb0 . Ainsi a0 |lb0 donc a0 |l ; car
pgcd(a0 , b0 ) = 1 (Ici nous avons utilisé le Lemme de Gauss que nous verrons dans
la prochaine section). Donc a0 b|lb et par conséquent m = a0 b|lb = n.

Proposition 2. Si a|c et b|c alors ppcm(a, b)|c.

Preuve. On pose m = ppcm(a, b). On considère la division euclidienne de

c par m : c = mq + r; 0 ≤ r < m. Cela implique que r = c − mq est un multiple
commun de a et b car c et m le sont ; par conséquent r = 0 et m|c.
Il serait faux de penser que ab|c. Par exemple 3|18, 9|18 mais 3 × 9 ne divise
pas 18. Par contre ppcm(3, 9) = 9 divise bien 18.

3 Relations de Bézout et de Gauss

Théorème 2 (Théorème de Bézout). Soient a, b des entiers. Il existe des entiers
u, v ∈ Z tels que au + bv = pgcd(a, b)

La preuve découle de l’algorithme d’Euclide. Les entiers u, v ne sont pas uniques.

Les entiers u, v sont des coefficients de Bézout. Ils s’obtiennent en remontant l’al-
gorithme d’Euclide.

Exemple 5. Calculer les coefficients de Bézout pour a = 560 et b = 133. Nous

utilisons pour cela les calculs effectués pour trouver pgcd(560, 133) = 7.

560 = 133 × 4 + 28
133 = 28 × 4 + 21
28 = 21 × 1 + 7
21 = 7 × 3 + 0

On exprime le pgcd à l’aide de la dernière ligne où le reste est non nul. Puis
on remplace le reste de la ligne précédente, et ainsi de suite jusqu’à arriver à la
première ligne.

7 = 28 − 21 × 1
= 28 − (133 − 28 × 4) × 1 = 28 × 5 − 133 × 1
= (560 − 133 × 4) × 5 − 133 × 1 = 560 × 5 − 133 × 21
Ainsi pour u = 5 et v = −21 alors 560 × 5 + 133 × (−21) = 7.

BP :64 Ouagadougou cité AN II Burkina Faso 4 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
Exercice 1. Calculons les coefficients de Bézout correspondant à pgcd(3471, 1599) =
39.

Corollaire 1. Si d|a et d|b alors d|pgcd(a, b).

Preuve. Comme d|au et d|bv donc d|au + bv. Par le Théorème de Bézout
d|pgcd(a, b).

Corollaire 2. Deux entiers. a et b sont premiers entre eux si et seulement si il

existe u, v ∈ Z tels que au + bv = 1

Preuve. La condition nécessaire est une conséquence du Théorème de Bé-

zout.
Pour la condition suffisante, on suppose qu’il existe u, v tels que au + bv = 1.
Comme pgcd(a, b)|a alors pgcd(a, b)|au. De même pgcd(a, b)|bv. Donc pgcd(a, b)|au+
bv = 1. Donc pgcd(a, b) = 1.

Remarque 3. Si on trouve deux entiers u0 , v 0 tels que au0 +bv 0 = d, cela n’implique
pas que d = pgcd(a, b). On sait seulement alors que pgcd(a, b)|d. Par exemple
a = 12, b = 8 ; 12 × 1 + 8 × 3 = 36 et pgcd(a, b) = 4.

Corollaire 3 (Lemme de Gauss). Soient a, b, c ∈ Z. Si a|bc et pgcd(a, b) = 1

alors a|c

Preuve. Comme pgcd(a, b) = 1 alors il existe u, v ∈ Z tels que au + bv = 1.

On multiplie cette égalité par c pour obtenir acu + bcv = c. Mais a|acu et par
hypothèse a|bcv donc a divise acu + bcv = c.

4 Nombres premiers
Les nombres premiers sont en quelque sorte les briques élémentaires des entiers
i.e. : tout entier s’écrit comme produit de nombres premiers.

Définition 5. Un nombre premier p est un entier ≥ 2 dont les seuls diviseurs

positifs sont 1 et p.

Exemple 6. Les entiers 2, 3, 5, 7, 11 sont premiers, 4 = 2 × 2, 6 = 2 × 3, 8 = 2 × 4

ne sont pas premiers.

Lemme 2. Tout entier n ≥ 2 admet un diviseur qui est un nombre premier.

Preuve. Soit D l’ensemble des diviseurs de n qui sont ≥ 2 :


D = k ≥ 2; k|n .

BP :64 Ouagadougou cité AN II Burkina Faso 5 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
L’ensemble D est non vide (car n ∈ D), notons alors p = min D.
Supposons, par l’absurde, que p ne soit pas un nombre premier alors p admet
un diviseur q tel que 1 < q < p mais alors q est aussi un diviseur de n et donc q ∈ D
avec q < p. Ce qui donne une contradiction car p est le minimum. Conclusion : p
est un nombre premier. Et comme p ∈ D, p divise n.
Proposition 3. Il existe une infinité de nombres premiers.
Preuve. Par l’absurde, supposons qu’il n’y ait qu’un nombre fini de nombres
premiers que l’on note p1 = 2, p2 = 3, p3 ,. . . , pn . Considérons l’entier N = p1 ×
p2 × · · · × pn + 1. Soit p un diviseur premier de N (un tel p existe par le lemme
précédent), alors d’une part p est l’un des entiers pi donc p|p1 × · · · × pn , d’autre
part p|N donc p divise la différence N − p1 × · · · × pn = 1. Cela implique que p = 1,
ce qui contredit que p soit un nombre premier.
Cette contradiction nous permet de conclure qu’il existe une infinité de nombres
premiers.
Remarque 4. Si un √ nombre n n’est pas premier alors un de ses facteurs est
inférieur ou égale à n.
En effet si n = a × b avec a, b√≥ 2. Sans perte de généralité, on peut supposer
a ≤ b ; alors a2 ≤ n ; d’où a ≤ n.
Par exemple pour tester si un nombre ≤ 100 est premier il suffit de tester les
diviseurs ≤ 10. Et comme il suffit de tester les diviseurs premiers, il suffit en fait
de tester la divisibilité par 2, 3, 5 et 7.
Proposition 4 (Lemme d’Euclide). Soit p un nombre premier. Si p|ab alors p|a
ou p|b.
Preuve. Si p ne divise pas a alors p et a sont premiers entre eux. En effet
les diviseurs de p sont 1 et p, mais seul 1 divise aussi a, donc pgcd(a, p) = 1. Ainsi
par le Lemme de Gauss p|b.
√
Exemple 7. Si p est un nombre premier, p n’est pas un nombre rationnel.
√
On fait une preuve par l’absurde. Supposons que p = ab avec a ∈ Z, b ∈ N∗ et
2
pgcd(a, b) = 1. Alors p = ab2 donc pb2 = a2 . Ainsi p|a2 donc par le Lemme d’Euclide
p|a. On peut alors écrire a = pa0 avec a0 un entier. De l’équation pb2 = a2 on tire
alors b2 = pa02 . Ainsi p|b2 et donc p|b. Maintenant p|a et p|b donc a et b ne sont
√
pas premiers entre eux. Ce qui contredit pgcd(a, b) = 1. Conclusion p n’est pas
rationnel.
Théorème 3. Soit n ≥ 2 un entier. Il existe des nombres premiers p1 < p2 <
· · · < pr et des exposants entiers α1 , α2 , . . . , αr ≥ 1 tels que :
n = pα1 1 × pα2 2 × · · · × pαr r .
De plus les pi et les αi (i = 1, . . . , r) sont uniques.

BP :64 Ouagadougou cité AN II Burkina Faso 6 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
 Preuve.
Existence. Nous allons démontrer l’existence de la décomposition par une récur-
rence sur n.
L’entier n = 2 est déjà décomposé. Soit n ≥ 3, supposons que tout entier
strictement inférieur à n admette une décomposition en facteurs premiers. Notons
p1 le plus petit nombre premier divisant n. Si n est un nombre premier alors n = p1
et c’est fini. Sinon on définit l’entier n0 = pn1 < n et on applique notre hypothèse de
récurrence à n0 qui admet une décomposition en facteurs premiers. Alors n = p1 ×n0
admet aussi une décomposition.

Unicité. Nous allons démontrer qu’une telle décomposition estPunique en ef-

fectuant cette fois une récurrence sur la somme des exposants σ = ri=1 αi .
Si σ = 1 cela signifie n = p1 qui est bien l’unique écriture possible.
Soit σ ≥ 2. On suppose que les entiers dont la somme des exposants est < σ
ont une unique décomposition. Soit n un entier dont la somme des exposants vaut
σ. Écrivons le avec deux décompositions :

n = pα1 1 × pα2 2 × · · · × pαr r = q1β1 × q2β2 × · · · × qsβs .

(On a p1 < p2 < · · · et q1 < q2 < · · · .)

Si p1 < q1 alors p1 < qj pour tous les j = 1, . . . , s. Ainsi p1 divise pα1 1 × pα2 2 ×
· · · × pαr r = n mais ne divise pas q1β1 × q2β2 × · · · × qsβs = n. Ce qui est absurde. Donc
p1 ≥ q1 .
Si p1 > q1 un même raisonnement conduit aussi à une contradiction. On conclut
que p1 = q1 . On pose alors
n
n0 = = pα1 1 −1 × pα2 2 × · · · × pαr r = q1β1 −1 × q2β2 × · · · × qsβs
p1

L’hypothèse de récurrence qui s’applique à n0 implique que ces deux décompositions

sont les mêmes. Ainsi r = s et pi = qi , αi = βi , i = 1, . . . , r.

Remarque 5. La principale raison pour laquelle on choisit de dire que 1 n’est

pas un nombre premier est dû au fait que dans le cas contraire, il n’y aurait plus
unicité de la décomposition : 24 = 23 × 3 = 1 × 23 × 3 = 12 × 23 × 3 = · · ·

Exemple 8.
560 = 25 × 5 × 7, 133 = 7 × 19.
Pour calculer le pgcd on réécrit ces décompositions :

560 = 24 × 51 × 71 × 190 , 133 = 20 × 50 × 71 × 191 .

BP :64 Ouagadougou cité AN II Burkina Faso 7 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
 Le pgcd est le nombre obtenu en prenant le plus petit exposant de chaque facteur
premier :
pgcd(560, 133) = 20 × 50 × 71 × 190 = 7.
Pour le ppcm on prend le plus grand exposant de chaque facteur premier :

ppcm(504, 300) = 24 × 51 × 71 × 191 = 10640

5 Congruences
Définition 6. Soit n ≥ 2 un entier. On dit que a est congru à b modulo n, si n
divise b − a. On note alors
a ≡ b (mod n).

On note aussi parfois a = b (mod n) ou a ≡ b[n]. Une autre formulation est

a ≡ b (mod n) ⇐⇒ ∃k ∈ Z; a = b + kn.
Remarquez que n divise a si et seulement si a ≡ 0 (mod n).

Proposition 5.

1. La relation « congru modulo n » est une relation d’équivalence.

2. Si a ≡ b (mod n) et c ≡ d (mod n) alors a + c ≡ b + d (mod n).
3. Si a ≡ b (mod n) et c ≡ d (mod n) alors a × c ≡ b × d (mod n).
4. Si a ≡ b (mod n) alors pour tout k ≥ 0, ak ≡ bk (mod n).

Preuve.
1. trivial.
2. trivial.
3. Prouvons la propriété multiplicative : a ≡ b (mod n) donc il existe k ∈ Z
tel que a = b + kn et c ≡ d (mod n) donc il existe l ∈ Z tel que c ≡ d + ln.
Alors a × c = (b + kn) × (d + ln) = bd + (bl + dk + kln)n qui est bien de la
forme bd + mn avec m ∈ Z. Ainsi ac ≡ bd (mod n).
4. C’est une conséquence du point précédent : avec a = c et b = d on obtient
a2 ≡ b2 (mod n). On continue le raisonnement par récurrence.

Exemple 9.
On a : 27 ≡ 10 (mod 17) ou encore 27 ≡ −7 (mod 17) ; 212022 ≡ 12022 ≡ 1
(mod 10).

BP :64 Ouagadougou cité AN II Burkina Faso 8 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
Remarque 6. Pour trouver un « bon » représentant de a (mod n) on peut aussi
faire la division euclidienne de a par n : a = bn + r alors a ≡ r (mod n) et
0 ≤ r < n.

Exemple 10. Les calculs bien menés avec les congruences sont souvent très ra-
pides. Par exemple on souhaite calculer 221 (mod 37) (plus exactement on souhaite
trouver 0 ≤ r < 37 tel que 221 ≡ r (mod 37)). Plusieurs méthodes :
1. On calcule 221 , puis on fait la division euclidienne de 221 par 37, le reste
est notre résultat. C’est laborieux !
2. On calcule successivement les 2k modulo 37 : 21 ≡ 2 (mod 37), 22 ≡ 4
(mod 37), 23 ≡ 8 (mod 37), 24 ≡ 16 (mod 37), 25 ≡ 32 (mod 37). En-
suite on n’oublie pas d’utiliser les congruences : 26 ≡ 64 ≡ 27 (mod 37).
27 ≡ 2 · 26 ≡ 2 · 27 ≡ 54 ≡ 17 (mod 37) et ainsi de suite en utilisant le
calcul précédent à chaque étape. C’est assez efficace et on peut raffiner : par
exemple on trouve 28 ≡ 34 (mod 37) mais donc aussi 28 ≡ −3 (mod 37) et
donc 29 ≡ 2 · 28 ≡ 2 · (−3) ≡ −6 ≡ 31 (mod 37),...
3. Il existe une méthode encore plus efficace, on écrit l’exposant 21 en base 2 :
21 = 24 + 22 + 20 = 16 + 4 + 1. Alors 221 = 216 · 24 · 21 . Et il est facile
de calculer successivement chacun de ces termes car les exposants sont des
puissances de 2. Ainsi 28 ≡ (24 )2 ≡ 162 ≡ 256 ≡ 34 ≡ −3 (mod 37) et
2
216 ≡ (28 ) ≡ (−3)2 ≡ 9 (mod 37). Nous obtenons 221 ≡ 216 · 24 · 21 ≡
9 × 16 × 2 ≡ 288 ≡ 29 (mod 37).

6 Applications
6.1 Équation de congruence ax ≡ b (mod n)
Proposition 6. Soit a ∈ Z∗ , b ∈ Z fixés et n ≥ 2. Considérons l’équation ax ≡ b
(mod n) d’inconnue x ∈ Z :
1. Il existe des solutions si et seulement si pgcd(a, n)|b.
n
2. Les solutions sont de la forme x = x0 + l pgcd(a,n) , l ∈ Z où x0 est une
solution particulière. Il existe donc pgcd(a, n) classes de solutions.

Preuve.

BP :64 Ouagadougou cité AN II Burkina Faso 9 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
 1.
x ∈ Z est un solution de l’équation ax ≡ b (mod n) (1)
⇐⇒ ∃k ∈ Z ax = b + kn (2)
⇐⇒ ∃k ∈ Z ax − kn = b (3)
⇐⇒ pgcd(a, n)|b (4)
(5)
Nous avons juste transformé notre équation ax ≡ b (mod n) en une équa-
tion ax−kn = b étudiée auparavant, seules les notations changent : au+bv =
c devient ax − kn = b.
2. Supposons qu’il existe des solutions. Nous allons noter d = pgcd(a, n) et
écrire a = da0 , n = dn0 et b = db0 (car par le premier point d|b). L’équation
ax − kn = b d’inconnues x, k ∈ Z est alors équivalente à l’équation a0 x −
kn0 = b0 , notée (?). Nous savons résoudre cette équation, si (x0 , k0 ) est une
solution particulière de (?) alors on connaît tous les (x, k) solutions. En
particulier x = x0 + ln0 avec l ∈ Z (les k ne nous intéressent pas ici).
n
Ainsi les solutions x ∈ Z sont de la forme x = x0 + l pgcd(a,n) , l ∈ Z où x0
est une solution particulière de ax ≡ b (mod n). Et modulo n cela donne
bien pgcd(a, n) classes distinctes.

Exemple 11. Résolvons l’équation 9x ≡ 6 (mod 24). Comme pgcd(9, 24) = 3 di-
vise 6 la proposition ci-dessus nous affirme qu’il existe des solutions. Nous allons
les calculer. (Il est toujours préférable de refaire rapidement les calculs que d’ap-
prendre la formule). Trouver x tel que 9x ≡ 6 (mod 24) est équivalent à trouver
x et k tels que 9x = 6 + 24k. Mis sous la forme 9x − 24k = 6 il s’agit alors
d’une équation que nous avons étudiée en détails. Il y a bien des solutions car
pgcd(9, 24) = 3 divise 6. En divisant par le pgcd on obtient l’équation équivalente :
3x − 8k = 2.
Pour le calcul du pgcd et d’une solution particulière nous utilisons normale-
ment l’algorithme d’Euclide et sa remontée. Ici il est facile de trouver une solution
particulière (x0 = 6, k0 = 2) à la main.
Si (x, k) est une solution de 3x − 8k = 2 alors par soustraction on obtient
3(x − x0 ) − 8(k − k0 ) = 0 et on trouve x = x0 + 8l, avec l ∈ Z (le terme k ne nous
intéresse pas). Nous avons donc trouvé les x qui sont solutions de 3x − 8k = 2,
ce qui équivaut à 9x − 24k = 6, ce qui équivaut encore à 9x ≡ 6 (mod 24). Les
solutions sont de la forme x = 6 + 8l. On préfère les regrouper en 3 classes modulo
24 :
x1 = 6 + 24m, x2 = 14 + 24m, x3 = 22 + 24m avec m ∈ Z.

BP :64 Ouagadougou cité AN II Burkina Faso 10 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
Remarque 7. Expliquons le terme de « classe » utilisé ici. Nous avons consi-
déré ici que l’équation 9x ≡ 6 (mod 24) est une équation d’entiers. On peut aussi
considérer que 9, x, 6 sont des classes d’équivalence modulo 24, et l’on noterait
alors 9x = 6. On trouverait comme solutions trois classes d’équivalence :
x1 = 6, x2 = 14, x3 = 22.

6.2 Petit théorème de Fermat

Lemme 3. p divise kp pour 1 ≤ k ≤ p − 1, c’est-à-dire kp ≡ 0 (mod p).

p p! p p




Preuve. k
= k!(p−k)!
donc p! = k!(p − k)! k
. Ainsi p|k!(p − k)! k
. Or
comme 1 ≤ k ≤ p − 1 alors p ne divise pas k! (sinon p divise l’un des facteurs de
k! mais il sont tous
< p). De même p ne divise pas (p − k)!, donc par le lemme
d’Euclide p divise kp .
Théorème 4 (Petit théorème de Fermat). Si p est un nombre premier et a ∈ Z
alors ap ≡ a (mod p)
Preuve. Nous le montrons par récurrence pour les a ≥ 0.
— Si a = 0 alors 0 ≡ 0 (mod p).
— Fixons a ≥ 0 et supposons que ap ≡ a (mod p). Calculons (a + 1)p à l’aide
de la formule du binôme de Newton :
     
p p p p−1 p p−2 p
(a + 1) = a + a + a + ··· + +1
p−1 p−2 1
Réduisons maintenant modulo p :
     
p p p p−1 p p−2 p
(a + 1) ≡ a + a + a + ··· + +1 (mod p)
p−1 p−2 1
≡ ap + 1 (mod p)
≡ a + 1 (mod p)

— Par le principe de récurrence nous avons démontré le petit théorème de

Fermat pour tout a ≥ 0. Le résultat est aussi vrai pour le cas des a ≤ 0 car
nous raisonnons modulo p.

Corollaire 4. Si p ne divise pas a alors ap−1 ≡ 1 (mod p)

Preuve. Si p ne divise pas a alors a et p sont premiers entre eux, car p est
premier. Mais comme ap − a = a(ap−1 − 1), alors d’après le Lemme de Gauss, p
divise ap−1 − 1 ; d’où le résultat.

BP :64 Ouagadougou cité AN II Burkina Faso 11 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE
Exemple 12. Calculons 20213395 (mod 17). Le nombre 17 étant premier on sait
par le petit théorème de Fermat que 202116 ≡ 1 (mod 17). Écrivons la division
euclidienne de 3395 par 16 :

3395 = 212 × 16 + 3.

Alors

20213395 ≡ 202116×212+3 ≡ 202116×212 × 20213

212
≡ 202116 × 20213 ≡ 1212 × 20213
≡ 20213 (mod 17)

De plus 2021 ≡ 15 (mod 17) ≡ −2 (mod 17).

Cela implique : 20213 (mod 17) ≡ −8 (mod 17) ≡ 9 (mod 17).
D’où : 20213395 ≡ 9 (mod 17)

Quelques ressources
1. [Link]
2. [Link]
3. [Link]
4. Les Méthodes et Exercices de Mathématiques (MPSI/PCSI/PTSI), Jean-Marie
MONIER, Dunod.
5. Maths MPSI-MP2I -Tout-en-un- 6e édition, Claude Deschamps, François Moulin,
Yoann Gentric et al., Dunod.

BP :64 Ouagadougou cité AN II Burkina Faso 12 Université Virtuelle du Burkina Faso

Site web : [Link] Courriel : info@[Link] une formation de qualité pour tous !
Joël KABORE