Chapitre 3

Arithmétique

3.0.4 Multiples et diviseurs

Définition 3.1 Soient a, b ∈ Z. On dit que a divise b ou que b est un multiple de a, s’il existe k ∈ Z tel
que a × k = b. On écrit a|b. On note D (a) l’ensemble des diviseurs de a et aZ l’ensemble des multiples
de a.

Exemple 3.1 1. 7|21 et 6|12.

2. a ∈ Z est pair ⇔ 2|a.

Proposition 3.1 1. ∀a ∈ Z, on a a|0 et 1|a.

2. ∀a ∈ Z, a|1 ⇒ a = +1 ou a = −1.

3. ∀a, b ∈ Z, a|b et b|a ⇒ b = ±a.

4. ∀a, b, c ∈ Z, ∀u, v ∈ Z, c|a et c|b ⇒ c|au + bv.

5. ∀x ∈ Z∗ , a|b ⇔ ax|bx.

Preuve : Pour le point 4. Soient c|a et c|b, alors ∃k ∈ Z tel que a = kc et ∃k0 ∈ Z tel que b = k0 c.
De plus, ∀u, v ∈ Z, on a au + bv = uck + vck0 = c(uk + vk0 ). Donc c|au + bv. 3 r
Pour le point 5. ∃k ∈ Z tel que b = ka ⇔ bx = kax ∀x ∈ Z∗ , ainsi ax|bx. 3 r

Théorème 3.1 (Division euclidienne).

Soient a ∈ Z et b ∈ Z∗ , alors ∃!(q, r ) ∈ Z2 tel que a = bq + r et 0 ≤ r < |b|.

Remarque 3.1 1. L’entier q s’appelle le quotient et l’entier r s’appelle le reste de la division euclidienne
de a par b.

2. r = 0 ⇔ b|a.

Exemple 3.2 Soient a = 6789 et b = 34, alors 6789 = 34 × 199 + 23. On a bien 0 ≤ 23 < 34.

27
28 CHAPITRE 3. ARITHMÉTIQUE
6789 | 34
34
-- ---------
338 | 199
306
--- |
329 |
306
--- |
23 |

3.0.5 PGCD de deux entiers

Définition 3.2 Soient a, b ∈ Z. Le plus grand entier qui divise à la fois a et b, s’appelle le plus grand
diviseur commun de a et b et se note P GCD (a, b) ou a ∧ b.

Remarque 3.2 La définition usuelle ne permet pas de définir 0 ∧ 0 puisqu’il n’existe pas de plus grand
diviseur de 0. On pose par convention : 0 ∧ 0 = 0.

Proposition 3.2 1. ∀a, b ∈ Z, on a a ∧ b ≥ 0.

2. Si a = 0 et b ∈ Z, alors 0 ∧ b = |b|.

3. ∀a, b, c ∈ Z, on a c|a et c|b ⇒ c|a ∧ b.

4. ∀a, b ∈ Z, a ∧ b = b ∧ a.

5. a ∧ ka = |a|, ∀k, a ∈ Z.

6. ∀a ∈ Z, a ∧ 1 = 1.

Exemple 3.3 On a 21 ∧ 14 = 7; 12 ∧ 32 = 4; 21 ∧ 26 = 1 et 0 ∧ −3 = 3.

Exercice 3.1 Soient a, b, c trois entiers non nuls. Montrer que a ∧ b = b ∧ (a − cb).

3.0.6 Algorithme d’Euclide

Lemme 3.1 Soient a ∈ Z et b ∈ Z∗ . Écrivons la division euclidienne a = bq + r. Alors

a ∧ b = b ∧ r = b ∧ (a − bq ).

Exemple 3.4 1. Soient a = 123 et b = 18. Calculons a ∧ b. On a 123 = 6 × 18 + 15, ce qui implique
123 ∧ 18 = 18 ∧ 15. De plus 18 = 1 × 15 + 3, donc 18 ∧ 15 = 15 ∧ 3 = 3. Par suite 123 ∧ 18 = 3.

2. De même, on a −28 ∧ 16 = 4.

ENSAM Casablanca
Couple de Bézout 29
3.0.7 Couple de Bézout
Théorème 3.2 ∀a, b ∈ Z, ∃(u, v ) ∈ Z2 tel que au + bv = a ∧ b. Le couple (u, v ) s’appelle couple
de Bézout.

Remarque 3.3 1. Un tel couple n’est pas unique, comme le montre l’exemple suivant

1×6−1×4 = 6∧4 = 2
−3 × 6 + 5 × 4 = 6 ∧ 4 = 2.

2. S’il existe (u, v ) ∈ Z2 tel que au + bv = d, alors a ∧ b divise d.

Exemple 3.5 Calculons le couple de Bézout pour a = 400 et b = 142. On a 400 ∧ 142 = 2. 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.

400 = 142 × 2 + 116

142 = 116 × 1 + 26
116 = 4 × 26 + 12
26 = 12 × 2 + 2
12 = 6 × 2 + 0.
De plus, on a
2 = 26 − 2 × 12
= 26 − 2(116 − 4 × 26)
= 26 − 2 × 116 + 8 × 26
= −2 × 116 + 9 × 26
= −2 × 116 + 9(142 − 116 × 1)
= 9 × 142 − 11 × 116
= 9 × 142 − 11(400 − 2 × 142)
= −11 × 400 + 31 × 142.
Ainsi u = −11 et v = 31.

Exercice 3.2 Calculer le couple de Bézout pour a = 200 et b = −28 en utilisant l’algorithme d’Euclide.

3.0.8 Nombres premiers entre eux

Définition 3.3 On dit que deux entiers a et b sont premiers entre eux, si a ∧ b = 1.

Exemple 3.6 Les deux entiers 9 et 14 sont premiers entre eux, car 9 ∧ 14 = 1.

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

Soient a, b ∈ Z. On a a ∧ b = 1 ⇔ ∃(u, v ) ∈ Z2 tel que au + bv = 1.

Preuve. On suppose que a ∧ b = 1. Alors ∃(u, v ) ∈ Z2 tel que au + bv = a ∧ b = 1.

Inversement, s’il existent u et v deux éléments de Z tels que au + bv = 1, alors a ∧ b divise 1.
Ainsi a ∧ b = 1 ou a ∧ b = −1. Or, a ∧ b ≥ 0, on en déduit que a ∧ b = 1. 3 r

ENSAM Casablanca
30 CHAPITRE 3. ARITHMÉTIQUE
Exercice 3.3 ∀a, b, c ∈ Z. Montrer que ac ∧ bc = |c|(a ∧ b).

Théorème 3.4 (théorème

( de Gauss).
a|bc
∀a, b, c ∈ Z. On a ⇒ a|c.
a∧b = 1

Preuve. ∃k ∈ Z tel que ka = bc, de plus, ∃(u, v ) ∈ Z2 tel que au + bv = 1. Alors

au + bv = 1 ⇒ cau + cbv = c
⇒ a(uc + vk ) = c ⇒ a|c. 3
r

Exercice 3.4 Soient a, b et c des éléments de Z. Montrer que


a|c


1. b|c ⇒ ab|c.
a∧b = 1



(
a∧c = 1
2. ⇒ ab ∧ c = 1.
b∧c = 1

3.0.9 PPCM de deux entiers

Définition 3.4 Soient a, b ∈ Z. On appelle plus petit multiple commun de a et b noté P P CM (a, b)
ou a ∨ b et est défini par :

1. si a = 0 ou b = 0 alors a ∨ b = 0.

2. si a , 0 et b , 0 alors a ∨ b = min({m ∈ N∗ | a|m et b|m}).

Exemple 3.7 On a 6 ∨ 8 = 24.

Remarque 3.4 1. ∀a, b, c ∈ Z, on a a|c et b|c ⇒ a ∨ b|c.

2. ∀a, b ∈ Z, a ∨ b = b ∨ a.

3.0.10 Nombre premier

Définition 3.5 Un nombre premier est un entier supérieur ou égal à 2 qui admet exactement deux divi-
seurs distincts entiers et positifs qui sont alors 1 et lui-même.

Exemple 3.8 1. Les nombres 2, 3, 5, 7, 11 sont des nombres premiers.

2. 1 n’est pas premier car il n’a qu’un seul diviseur entier positif ; 0 non plus car il est divisible par tous
les entiers positifs.

Proposition 3.3 Soient n, p ∈ Z tel que p > 1. Alors, les assertions suivantes sont équivalentes :

1. p est premier.

ENSAM Casablanca
Congruence 31
2. p - n ⇔ p ∧ n = 1.

3. ∀k ∈ ~1, p − 1, p ∧ k = 1.

Exercice 3.5 Soit p est premier. Montrer que p|ab ⇒ p|a ou p|b.

Théorème 3.5 (théorème fondamental de l’arithmétique).

Tout entier naturel n ≥ 2 peut s’écrire de manière unique sous la forme :
αk
n = pα α2
1 × p2 × . . . × p k ,
1
(3.1)

où

1. pi sont des nombres premiers tels que p1 < p2 < ... < pk .

2. αi sont des entiers naturels avec 1 ≤ i ≤ k.

La décomposition (3.1) s’appelle la décomposition en facteur premier de n.

Remarque 3.5 Ce résultat reste vrai pour n ∈ Z.

αk β β β
Proposition 3.4 Soient n = pα 1 α2
1 × p2 × . . . × pk et m = p1 × p2 × . . . × pk . Alors
1 2 k

min{α1 ,β1 } min{α2 ,β2 } min{αk ,βk }

n ∧ m = p1 × p2 × . . . × pk

et
max{α1 ,β1 } max{αk ,βk }
n ∨ m = p1 × pmax{α2 ,β2 } × . . . × pk .

Exemple 3.9 Soient a = 36 et b = 24. Calculons a ∨ b et a ∧ b.

Exercice 3.6 Montrer que ∀a, b ∈ Z, (a ∧ b)(a ∨ b) = |ab|.

3.0.11 Congruence
Proposition 3.5 ∀n ∈ N∗ , ∀(a, b, c, d) ∈ Z4 avec a ≡ b[n] et c ≡ d[n], on a

a) a + c ≡ b + d[n].

b) ac ≡ bd[n].

c) ∀k ∈ N, on a ak ≡ bk [n].
n
Exercice 3.7 1. Démontrer que, pour tout entier n ∈ N, 103 − 1 ≡ 0[3n+2 ].

2. Déterminer le chiffre des unités

. de 2016 2017

Théorème 3.6 (Petit théorème de Fermat).

Soit p un nombre premier. Alors, on a

ENSAM Casablanca
32 CHAPITRE 3. ARITHMÉTIQUE
a) ∀n ∈ Z, np ≡ n[p].

b) Pour tout entier n n’est pas divisible par p, on a np−1 ≡ 1[p].

Preuve.

a) On considère l’assertion (Pn ) : np ≡ n[p]. Il est clair que (P0 ) est vraie puisque pour tout p > 0
on a 0p ≡ 0[p]. Supposons que (Pn ) est vraie et montrons que (Pn+1 ) est vraie. On a d’après
p−
X1
la formule de binôme (n + 1)p − np − 1 = Cpk nk . Or, p divise Cpk , ∀k ∈ ~1, p − 1, car
k =1
k−1
kCpk = pCp− p p
1 . Ainsi, (n + 1) ≡ n + 1[p] ≡ n + 1[p]. On en déduit que (Pn ) est vraie.

b) Soit n un entier non divisible par p tel que n ∧ p = 1. Or, on a d’après le point précédent p divise
np − n i.e., p divise n(np−1 − 1). Comme p ∧ n = 1, alors d’après Gauss p divise np−1 − 1. Alors
np−1 ≡ 1[p]. 3r

Exemple 3.10 On a 1011 ≡ 10[11] et 812 ≡ 1[13].

3.0.12 Equation de type ax + by = c

On appelle équation diophantienne toute équation à inconnues entières. Pour résoudre l’équation :

ax + by = c, (3.2)

d’inconnues x, y ∈ Z et de coefficients a, b, c ∈ Z, on procède de la manière suivante :

1. Simplification par a ∧ b. On calcule d = a ∧ b. Si d ne divise pas c, alors il n’y a pas de solutions.

Sinon on divise l’équation par d et on aboutit l’équation

a0 x + b0 y = c0 , (3.3)

avec a0 ∧ b0 = 1. Donc résoudre (3.2) revient a résoudre (3.3).

2. Recherche d’une solution particulière. Soit il existe une solution particulière évidente, soit on la
trouve en écrivant une relation de Bézout entre a0 et b0 .

3. Recherche de la solution générale. Soit (x0 , y0 ) une solution particulière. Ainsi (x, y ) est solution
si et seulement si a0 (x − x0 ) + b0 (y − y0 ) = 0. Une utilisation du théorème de Gauss permet de
conclure que les solutions de (3.3) sont les couples (x0 + kb0 , y0 − ka0 ) avec k ∈ Z.

Exemple 3.11 Résolvons dans Z2 les équations suivantes :

1. 6x − 8y = 5.

2. 6x − 8y = 4.

Exercice 3.8 Résoudre dans Z2 l’équation suivante : 16x + 28y = 12.

ENSAM Casablanca
40 CHAPITRE 3. ARITHMÉTIQUE
3.2.1 Équation de congruence ax ≡ b[n]
Théorème 3.6 Soit n > 1 un entier et c un entier premier avec n. Alors il existe un entier c0 tel que

cc0 ≡ 1[n].

Un tel entier c0 est appelé un inverse de c modulo n.

Démonstration. Il s’agit d’une simple application du théorème de Bézout. Comme n et c sont premiers
entre eux, on peut écrire une égalité du type Un +V c = 1. On voit directement que l’entier c0 = V convient
pour le théorème. 3
r
Exemple 3.13 On a 7 × 3 ≡ 1[10]. Donc 3 est l’inverse de 7 modulo 10.

Proposition 3.13 Soient n > 1 un entier et a, b et c des entiers tels que ac ≡ bc[n]. Si c ∧ n = 1, alors on
peut déduire que a ≡ b[n].

Démonstration. Comme c ∧ n = 1, il admet un inverse modulo n, disons c0 . En multipliant par c0 la

congruence ac ≡ bc[n], on obtient directement le résultat. 3
r
Exemple 3.14 On a 2x ≡ 3[5]. Comme 2 ∧ 5 = 1, alors x ≡ 20 × 3[5], où 20 l’inverse de 2 modulo 5. Il est
clair que 20 = −2. Ainsi x ≡ −2 × 3[5] ≡ −1[5].

Proposition 3.14 Soit a ∈ Z∗ , b ∈ Z fixés et n ≥ 2. Considérons l’équation

ax ≡ b[n], (3.6)

d’inconnue x ∈ Z. Alors
1. Il existe des solutions si et seulement si a ∧ n|b.
2. En divisant l’équation (3.6) par a ∧ n, on obtient

a0 x ≡ b0 [n0 ], (3.7)
a b n
où a0 = , b0 = et n0 = avec a0 ∧ n0 = 1. Alors
a∧n a∧n a∧n
x ≡ a00 × b0 [n0 ], (3.8)

où a00 est l’inverse de a0 modulo n0 .

Exemple 3.15 Résolvons les équations suivantes

1. 9x ≡ 4[18].
2. 9x ≡ 6[24].

Solution.
1. L’équation n’admet pas de solution dans Z, car 9 ∧ 18 = 9 ne divise pas 4. 3
r

ENSAM Casablanca
 2. Comme 9 ∧ 24 = 3 divise 6 la Proposition 3.14 nous affirme qu’il existe des solutions. En divisant
par 9 ∧ 24 = 3, on obtient l’´equation 3x ≡ 2[8]. Ici 3 ∧ 8 = 1, donc x ≡ a × 2[8]. Il est facile de montrer
que a= −5. Donc x ≡ −10[8] ≡ −2[8] ≡ 6[8] i.e, les solutions sont de la forme x = 6 + 8k, k ∈ Z. r

Remarque 3.9 On peut les regrouper en 3 classes modulo 24 i.e, x = 6 + 24k, x = 14 + 24k, x = 22 + 24k
1 2 3
avec k ∈ Z. Dans ce cas, on a x1= 6, x 2= 14 et x = 22. Il y a 9 ∧ 24 classes modulo 24.
3