Algèbre et Arithmétique

Université libanaise

Ali Ayad
Professeur assistant à l’université libanaise - Section 1
[Link]@[Link]

Cours & Exercices proposés

2020
 Algèbre et Arithmétique

c Tous droits reservés

2020

c Ali Ayad page 2

Table des matières

1 Arithmétique dans Z 4
1.1 Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Plus grand commun diviseur . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Algorithme d’Euclide étendu . . . . . . . . . . . . . . . . . . . . 6
1.1.4 Entiers premiers entre eux . . . . . . . . . . . . . . . . . . . . . 8
1.1.5 Plus petit commun multiple . . . . . . . . . . . . . . . . . . . . 9
1.2 Décomposition en facteurs premiers . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Théorème fondamental de l’arithmétique . . . . . . . . . . . . . . 10
1.3 L’équation Diophantienne ax + by = c . . . . . . . . . . . . . . . . . . 11
1.4 Congruences modulo un entier . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Inversibles modulo un entier naturel n . . . . . . . . . . . . . . . . . . . 17
1.6 L’équation de congruence ax ≡ b (mod n) . . . . . . . . . . . . . . . 19
1.7 Le petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3
Chapitre 1

Arithmétique dans Z

1.1 Divisibilité
1.1.1 Définitions et propriétés
Définition 1.1.1 Soient a, b ∈ Z.
1) On dit que a divise b et on écrit a | b s’il existe c ∈ Z tel que b = ac. Dans ce cas,
on dit que b est divisible par a ou que b est un multiple de a, on dit aussi que a est
un diviseur de b. Si a ne divise pas b, alors on écrit a - b.
2) Soit k ∈ N. On dit que ak divise exactement b, et on écrit ak k b si ak divise b et
ak+1 ne divise pas b, i.e., k est le plus grand entier naturel tel que ak divise b.

Exemple 1.1.1
1) 42 divise le nombre 630 car 630 = 42 × 15.
2) Le nombre 14 est divisible par 1, 2, 7, 14, −1, −2, −7 et −14.
3) Le nombre 0 est divisible par tout entier. Le nombre 1 n’est divisible que par 1 et −1.
4) 33 k 540.

Proposition 1.1.1 Si a, b, c ∈ Z, alors

1) a | a.
2) Si a | b et b | a, alors a = ±b.
3) Si a | b et b | c, alors a | c.
4) Si a | b, alors a | bc.
5) Si a | b et a | c, alors a | ub + vc pour tous u, v ∈ Z.

Preuve Exercice. 2

4
Chapitre 1 Arithmétique dans Z

Remarque 1.1.1
1) Tout entier a est divisible par ±1 et ±a qu’on les appelle les diviseurs triviaux de
a. Un diviseur de a est dit propre s’il est différent de ±1 et de ±a. Par exemple, les
diviseurs propres de 12 sont ±2, ±3, ±4 et ±6. Le nombre 19 n’a pas de diviseurs
propres.
2) Si a divise b et b 6= 0, alors |a| ≤ |b| et si a est un diviseur propre de b, alors
1 < |a| < |b|.

Théorème 1.1.1 (Division Euclidienne dans Z)

Pour tout couple d’entiers (a, b) ∈ Z × Z tel que b 6= 0, il existe un et un seul couple
d’entiers (q, r) ∈ Z × Z tel que a = bq + r avec 0 ≤ r < |b|. On appelle q le quotient
et r le reste de la division euclidienne de a par b dans Z.

Exemple 1.1.2
1) Si a = 35 et b = 8, la relation 35 = 4 × 8 + 3 est une division euclidienne dans N.
2) Si a = −35 et b = 8, la relation −35 = (−4) × 8 + (−3) n’est pas une division
euclidienne dans Z car le reste d’une division euclidienne doit être positif ou nul. Par
contre, l’écriture −35 = (−5) × 8 + 5 est bien une division euclidienne dans Z.
3) Si a = −35 et b = −8, la relation −35 = 5(−8) + 5 est une division euclidienne
dans Z.

1.1.2 Plus grand commun diviseur

Définition 1.1.2 Soient a et b deux entiers de Z tels que (a, b) 6= (0, 0). On dit qu’un
entier d est un plus grand commun diviseur (pgcd) de a et b si les deux conditions suiv-
antes sont vérifiées :
i) d divise a et d divise b, i.e., d est un diviseur commun de a et b.
ii) si c ∈ Z tel que c divise a et c divise b, alors c divise d.

Remarque 1.1.2
1) Si d1 et d2 sont deux pgcd de a et b, alors d1 = ±d2 , donc l’un d’eux est positif
et l’autre est négatif, celui qui est positif s’appelle le plus grand commun diviseur de
a et b, il est noté par pgcd(a, b) ou a ∧ b.
2) Si a = b = 0, alors on pose pgcd(a, b) = 0.

c Ali Ayad page 5

Chapitre 1 Arithmétique dans Z

Théorème 1.1.2 (Algorithme d’Euclide)

Si a, b ∈ Z tels que b 6= 0, alors a et b possèdent un pgcd. Plus précisement, on pose
r0 = a et r1 = b et, pour tout k ≥ 2, rk est le reste de la division euclidienne de rk−2
par rk−1 , alors la suite d’entiers (rk )k≥0 se termine, i.e., il existe N ∈ N tel que

rN +1 = 0 et rk 6= 0, ∀ 0 ≤ k ≤ N.

De plus, rN est le pgcd de a et b, i.e., rN = a ∧ b.

Proposition 1.1.2 Soit a, b ∈ Z tels que (a, b) 6= (0, 0). Si d = a ∧ b, alors il existe
u, v ∈ Z tels que d = ua + vb.

Remarque 1.1.3 Soit a, b ∈ Z tels que (a, b) 6= (0, 0).

1) Si d = a ∧ b, alors les entiers u et v (proposition 1.1.2) tels que d = ua + vb ne
sont pas uniques. Par exemple, 35 ∧ 497 = 7 avec

7 = (−14)(35) + (1)(497) = (57)(35) + (−4)(497).

2) La réciproque de la proposition 1.1.2 n’est pas vraie en général, i.e., s’il existe
u, v ∈ Z tels que d = ua + vb, alors d n’est pas nécessairement un pgcd de a et
b. Par exemple, 8 = (−2)(3) + (2)(7), mais 8 n’est pas un pgcd de 3 et 7 car
3 ∧ 7 = 1. Par contre, si d est un diviseur commun de a et b et s’il existe u, v ∈ Z
tels que d = ua + vb, alors d est un pgcd de a et b. En effet, si c ∈ Z est un
diviseur commun de a et b, alors c divise ua + vb, donc c divise d. Ainsi d est un
pgcd de a et b.

1.1.3 Algorithme d’Euclide étendu

Le théorème suivant donne une méthode calculatoire pour trouver des entiers u, v ∈ Z
tels que a ∧ b = ua + vb (où a, b ∈ Z tels que a ≥ b > 0).

Théorème 1.1.3 (Algorithme d’Euclide étendu)

Soit d = a ∧ b où a, b ∈ Z tels que a ≥ b > 0. On pose r0 = a et r1 = b et, pour tout
k ≥ 2, rk et qk−1 sont le reste et le quotient de la division euclidienne de rk−2 par rk−1
respectivement. Soit N ∈ N tel que rN = d (proposition 1.1.2). On construit par marche
inverse la suite d’entiers yN , yN −1 , . . . , y1 , y0 par yN = 0, yN −1 = 1 et

yk−1 = qk yk + yk+1 , ∀ 1 ≤ k ≤ N − 1.

Alors, pour tout 1 ≤ k ≤ N ,

d = (−1)N +k+1 rk−1 yk + (−1)N +k rk yk−1 .

c Ali Ayad page 6

Chapitre 1 Arithmétique dans Z

En particulier, pour k = 1, on obtient d = ua + vb avec

u = (−1)N y1 et v = (−1)N +1 y0 .

Remarque 1.1.4 En pratique, l’algorithme d’Euclide étendu se présente sous forme d’un
tableau à trois colonnes :
– Dans la première colonne, on place les restes rk .
– Dans la deuxième colonne, on place les quotients qk à partir de la deuxième ligne.
– Dans la troisième colonne, on place les yk en procédant de bas en haut en ignorant
la dernière ligne contenant le reste 0 et en mettant 0 et 1 sur les précédentes
respectivement.

Restes Quotients y
r0 − y0
r1 q1 y1
r2 q2 y2
.. .. ..
. . .
rk qk yk
.. .. ..
. . .
rN −1 qN −1 1
rN qN 0
0 − −

Exemple 1.1.3
1) Soit a = 187 et b = 132.

Restes Quotients y
187 − 7
132 1 5
55 2 2
22 2 1
11 2 0
0 − −

Donc a ∧ b = 11 = ua + vb avec u = 5 et v = −7.

2) Si a = −187 et b = 132, alors

a ∧ b = 11 = (−5)a + (−7)b.

c Ali Ayad page 7

Chapitre 1 Arithmétique dans Z

1.1.4 Entiers premiers entre eux

Définition 1.1.3 Soit a, b ∈ Z tels que (a, b) 6= (0, 0). On dit que a et b sont premiers
entre eux (ou que a est premier avec b) si 1 est un pgcd de a et b.

Lemme 1.1.1 (Lemme de Bézout)

Soit a, b ∈ Z tels que (a, b) 6= (0, 0). Alors a et b sont premiers entre eux si et seulement
s’il existe u, v ∈ Z tels que 1 = ua + vb.

Preuve
C.N. Si a et b sont premiers entre eux, alors 1 = a ∧ b, et donc il existe u, v ∈ Z tels
que 1 = ua + vb d’après le théorème 1.1.2.
C.S. Supposons qu’il existe u, v ∈ Z tel que 1 = ua + vb. Soit d = a ∧ b, alors d divise
a et d divise b, donc d divise ua + vb = 1, mais d > 0, alors d = 1. Ainsi a et b sont
premiers entre eux. 2

Proposition 1.1.3 Soit a, b ∈ Z tels que (a, b) 6= (0, 0).

a b
1) Si d = a ∧ b, alors ad ∧ db = 1, i.e.,



et sont premiers entre eux.
d d
2) Si d ∈ N∗ est un diviseur commun de a et b tel que ad ∧ db = 1, alors a ∧ b = d.

Preuve
1) Soit a0 = ad ∈ Z et b0 = db ∈ Z, alors a = a0 d et b = b0 d. Comme d = a ∧ b,
alors il existe u, v ∈ Z tels que d = ua + vb. Donc

d = ua + vb = ua0 d + vb0 d = (ua0 + vb0 )d.

Mais d 6= 0, alors 1 = ua0 + vb0 , donc, d’après le lemme de Bézout,

   
a b
∧ = a0 ∧ b0 = 1
d d

2) Si ad ∧ db = 1, alors il existe u, v ∈ Z tels que

   
a b
1=u +v .
d d
Donc d = ua + vb. De plus, comme d est un diviseur commun de a et b, alors
a ∧ b = d. 2

Proposition 1.1.4 Soit m, n ∈ N∗ deux entiers premiers entre eux et a ∈ Z un entier

tels que m divise a et n divise a, alors mn divise a.

c Ali Ayad page 8

Chapitre 1 Arithmétique dans Z

Preuve Puisque m divise a et n divise a, alors il existe α, β ∈ Z tels que a = αm

et a = βn. Comme m et n sont premiers entre eux, alors il existe u, v ∈ Z tels que
1 = um + vn. Donc

a = 1.a = (um + vn)a = uma + vna

= um(βn) + vn(αm) = (uβ + vα)mn,

avec uβ + vα ∈ Z. Ainsi mn divise a. 2

Lemme 1.1.2 (Lemme de Gauss)

Soit a, b, c ∈ Z − {0}. Si a divise bc et a est premier avec b, alors a divise c.

Preuve Comme a est premier avec b, alors il existe u, v ∈ Z tels que 1 = ua + vb.
En multipliant cette égalité par c, on obtient c = uac + vbc. Puisque a divise bc et a
divise uac, alors a divise uac + vbc, ainsi a divise c. 2

1.1.5 Plus petit commun multiple

Définition 1.1.4 Soit a, b ∈ Z deux entiers non nuls. On dit qu’un entier m est un plus
petit commun multiple (ppcm) de a et b si les deux conditions suivantes sont vérifiées :
i) m est un multiple commun de a et b.
ii) si c ∈ Z − {0} est un multiple commun de a et b, alors c est un multiple de m.

Remarque 1.1.5 Si m1 et m2 sont deux ppcm de a et b, alors m1 = ±m2 , donc l’un

d’eux est positif et l’autre est négatif, celui qui est positif s’appelle le plus petit commun
multiple de a et b, il est noté par ppcm(a, b) ou a ∨ b.

Théorème 1.1.4 Soit a, b ∈ Z − {0}. Si d = a ∧ b et m = a ∨ b, alors

md = |ab|.

1.2 Décomposition en facteurs premiers

1.2.1 Nombres premiers
Définition 1.2.1 Un nombre premier est un entier p ≥ 2, dont ses seuls diviseurs
positifs sont 1 et p lui-même. Un entier n ≥ 2 est dit composé s’il n’est pas premier.

c Ali Ayad page 9

Chapitre 1 Arithmétique dans Z

Remarque 1.2.1 Un entier p ≥ 2 est premier si et seulement si, pour tous a, b ∈ N,

la relation p = ab implique a = 1 ou b = 1. Les nombres 2, 3, 5, 7, 11, . . . , 2003, . . .
sont premiers, et les nombres 4, 6, 8, 9, 10, . . . , 2005, . . . sont composés.

Proposition 1.2.1 Si p est un nombre premier et a ∈ Z, alors p divise a ou p est

premier avec a.
Preuve Soit d = p ∧ a. Puisque p est premier et d est un diviseur positif de p, alors
d = 1 ou d = p. Si d = 1, alors p et a sont premiers entre eux, et si d = p, alors p
divise a. 2

1.2.2 Théorème fondamental de l’arithmétique

Lemme 1.2.1 (Lemme d’Euclide)
Soit a, b ∈ Z et p un nombre premier. Si p divise ab, alors p divise a ou p divise b.
Preuve Si p ne divise pas a, alors p est premier avec a par la proposition 1.2.1. Donc p
divise ab et p est premier avec a, ainsi p divise b par le lemme de Gauss. 2

Proposition 1.2.2 Tout entier n ≥ 2 est divisible par un nombre premier. Plus
précisement, le plus petit diviseur positif p ≥ 2 de n est premier.
x Preuve Soit n un entier tel que n ≥ 2. Notons Bn l’ensemble des diviseurs positifs d
de n tel que d ≥ 2, i.e.,
n o
Bn = d ∈ N, d | n et d ≥ 2 .
Il est clair que n ∈ Bn , donc Bn est une partie non vide de N. Il s’ensuit que Bn possède
un plus petit élément p. Montrons que p est un nombre premier. En effet, si p n’est pas
premier, alors p admet un diviseur propre positif k (i.e., 2 ≤ k < p). Comme k divise p
et p divise n, alors k divise n, et par suite k ∈ Bn , donc p ≤ k car p est le plus petit
élément de Bn , ainsi k < p ≤ k, ce qui est impossible. D’où p est un diviseur premier
de n. 2

Proposition 1.2.3
√ Si n ≥ 2 est un entier composé, alors n admet un diviseur premier
p tel que p ≤ n.
Preuve Soit p le plus petit diviseur premier de n (proposition 1.2.2). Puisque n est
composé, alors il existe un entier k ≥ 2 tel que n = pk, l’entier k admet un diviseur
premier q qui est aussi un diviseur premier de n. Donc p ≤ q ≤ k, et par suite
p2 ≤ pq ≤ pk = n.
√
Ainsi p ≤ n. 2

c Ali Ayad page 10

Chapitre 1 Arithmétique dans Z

Remarque 1.2.2 D’après la proposition√1.2.3, tout entier naturel n ≥ 2,

Q qui n’est pas
divisible par aucun nombre premier p ≤ n, est premier. Désignons par p le produit
√
p≤ n
√
de tous les nombres premiers inférieurs ou égaux à n. Ainsi un nombre n ≥ 2 est
premier si et seulement si  
Y
pgcd n, p = 1.
√
p≤ n

Dépuis Euclide, on sait que l’ensemble P des nombres premiers est infini.

P = {2, 3, 5, 7, 11, 13, 17, . . . , 219937 − 1, . . .}.

Proposition 1.2.4 (Euclide)

Il existe une infinité de nombres premiers.

Preuve Supposons, par l’absurde, que l’ensemble des nombres premiers est fini et notons
par p1 , . . . , pr tous les nombres premiers. Soit n = p1 · · · pn + 1 ∈ N∗ , alors, d’après la
proposition 1.2.2, il existe un nombre premier pi qui divise n pour un certain 1 ≤ i ≤ r.
Donc pi divise n et pi divise le produit p1 · · · pn , par suite pi divise n − p1 · · · pn = 1,
i.e., pi divise 1, ce qui est impossible. D’où l’ensemble des nombres premiers est infini. 2

Théorème 1.2.1 (Théorème fondamental de l’arithmétique)

Tout entier n ≥ 2 s’écrit sous la forme :

n = pk11 · · · pkr r

où r ∈ N∗ , p1 , . . . , pr sont de nombres premiers deux à deux distincts et k1 , . . . , kr ∈ N∗ .

Cette écriture est unique à l’ordre près des facteurs premiers, on l’appelle la factorisation
ou la décomposition de n en produit de nombres premiers.

Par exemple,

17 = 171 , 3528 = 23 32 72 et 8847 819 = 33 672 73.

1.3 L’équation Diophantienne ax + by = c

Théorème 1.3.1 Soit a, b, c ∈ Z tels que (a, b) 6= (0, 0) et d = a ∧ b.
1) L’équation Diophantienne ax + by = c admet de solutions (x, y) ∈ Z × Z si et
seulement si d divise c.

c Ali Ayad page 11

Chapitre 1 Arithmétique dans Z

2) Si d divise c et si (x0 , y0 ) ∈ Z × Z est une solution particulière, alors l’ensemble

des solutions de l’équation Diophantienne ax + by = c est donné par :
  
 x = x0 + k b
 d
 y = y0 − k a où k ∈ Z.
d

Preuve
1) C.N. Soit (x0 , y0 ) ∈ Z × Z une solution de l’équation Diophantienne ax + by = c,
alors ax0 + by0 = c. Comme d divise a et d divise b, alors d divise ax0 + by0 ,
donc d divise c.
C.S. Si d divise c, alors il existe c0 ∈ Z tel que c = dc0 . Comme d = a ∧ b, alors il
existe u, v ∈ Z tels que d = ua + vb, donc
c = dc0 = a(uc0 ) + b(vc0 ).
Ainsi (x0 , y0 ) = (uc0 , vc0 ) ∈ Z × Z est une solution de l’équation ax + by = c.
2) Supposons que d divise c et que (x0 , y0 ) ∈ Z × Z est une solution particulière. Si
(x, y) ∈ Z × Z est une solution quelconque de cette équation, alors
c = ax + by = ax0 + by0
et par suite
a(x − x0 ) = b(y0 − y).
Comme d divise a et b, alors il existe a0 , b0 ∈ Z tel que a = da0 et b = db0 , donc
da0 (x − x0 ) = db0 (y0 − y). Comme d 6= 0, alors
a0 (x − x0 ) = b0 (y0 − y)
Donc b0 divise a0 (x − x0 ) et comme b0 est premier avec a0 , alors b0 divise (x − x0 )
d’après le lemme de Gauss, donc il existe k ∈ Z tel que x − x0 = kb0 , ainsi
b
0
x = x0 + kb = x0 + k .
d
Donc a0 kb0 = b0 (y0 − y), et par suite y0 − y = ka0 (car b0 6= 0), donc
a
y = y0 − ka0 = y0 − k .
d
Réciproquement, s’il existe k ∈ Z tel que x = x0 + kb0 et y = y0 − ka0 , alors
ax + by = ax0 + akb0 + by0 − bka0
= ax0 + by0 + da0 kb0 − db0 ka0
= ax0 + by0 = c.
Donc (x, y) est une solution de l’équation. 2

c Ali Ayad page 12

Chapitre 1 Arithmétique dans Z

Exemple 1.3.1 Soit à résoudre, dans Z × Z, l’équation Diophantienne 71x + 32y = 7.

Pour trouver une solution particulière, on utilise l’algorithme d’Euclide étendu :

Restes Quotients y
71 − 20
32 2 9
7 4 2
4 1 1
3 1 1
1 3 0
0 − −

Donc 71 ∧ 32 = 1 divise 7, par suite l’équation admet de solutions dans Z × Z. D’après

ce tableau, on a
71(−9) + (32)(20) = 1 (∗)
En multipliant (∗) par 7, on obtient :

71(−63) + (32)(140) = 7.

Donc (−63, 140) est une solution particulière de l’équation 71x + 32y = 7. Ainsi la
solution générale de cette équation est donnée par :

x = −63 + 32k
y = 140 − 71k où k ∈ Z.

1.4 Congruences modulo un entier

Définition 1.4.1 Soit n ∈ N∗ et a, b ∈ Z. On dit que a est congru à b modulo n, et on
écrit a ≡ b (mod n), si n divise a − b. Autrement dit, a ≡ b (mod n) si et seulement
s’il existe k ∈ Z tel que a = b + nk.

Proposition 1.4.1 Soit n ∈ N∗ . La congruence modulo n est une relation d’équivalence

dans Z, i.e., pour tous a, b, c ∈ Z,
1) a ≡ a (mod n).
2) Si a ≡ b (mod n), alors b ≡ a (mod n).
3) Si a ≡ b (mod n) et b ≡ c (mod n), alors a ≡ c (mod n).

Preuve
1) Comme a − a = 0, alors n divise a − a, donc a ≡ a (mod n).

c Ali Ayad page 13

Chapitre 1 Arithmétique dans Z

2) Comme a ≡ b (mod n), alors il existe k ∈ Z tel que a−b = nk, donc b−a = nk0
où k0 = −k ∈ Z. Ainsi b ≡ a (mod n).
3) Comme a ≡ b (mod n) et b ≡ c (mod n), alors n divise a − b et n divise
b − c, par suite n divise (a − b) + (b − c) = a − c, donc n divise a − c, i.e.,
a ≡ c (mod n). 2

Proposition 1.4.2 Soit n ∈ N∗ et a, b ∈ Z tels que a ≡ b (mod n).

1) Pour tout c ∈ Z,

a+c≡b+c (mod n) et ac ≡ bc (mod n).

2) Pour tout k ∈ N,
ak ≡ bk (mod n).
3) Pour tout polynôme f (X) ∈ Z[X] à coefficients entiers,

f (a) ≡ f (b) (mod n).

Proposition 1.4.3 Soit n ∈ N∗ .

1) Si a, b ∈ Z, alors a ≡ b (mod n) si et seulement si a et b ont le même reste dans
la division euclidienne par n.
2) Pour tout a ∈ Z, il existe un et un seul entier r ∈ {0, 1, . . . , n − 1} tel que

a≡r (mod n).

Preuve
1) Soient r1 et r2 les restes des divisions euclidiennes de a et b par n respectivement,
alors 
a = nq1 + r1
b = nq2 + r2
où q1 , r1 , q2 , r2 ∈ Z tels que 0 ≤ r1 < n et 0 ≤ r2 < n. Donc

a − b = n(q1 − q2 ) + r1 − r2 .

C.N. Si a ≡ b (mod n), alors n divise a − b, donc n divise (a − b) − n(q1 − q2 ),

i.e., n divise r1 − r2 . Si r1 6= r2 , alors n ≤ |r1 − r2 |. Mais 0 ≤ r1 < n et
0 ≤ r2 < n, alors −n < r1 − r2 < +n, et donc |r1 − r2 | < n, ainsi n < n, ce
qui est impossible. D’où r1 = r2 .
C.S. Si r1 = r2 , alors r1 − r2 = 0 et donc

a − b = n(q1 − q2 )

avec q1 − q2 ∈ Z. Ce qui prouve que a ≡ b (mod n).

c Ali Ayad page 14

Chapitre 1 Arithmétique dans Z

2) Soient a ∈ Z et r le reste de la division euclidienne de a par n, alors a = nq + r

où q ∈ Z et 0 ≤ r < n. Donc a − r = nq et par suite a ≡ r (mod n). S’il existe
r 0 ∈ {0, 1, . . . , n − 1} tel que a ≡ r 0 (mod n), alors a et r 0 ont le même reste
dans la division euclidienne par n d’après la partie (1). Mais r 0 = 0n + r 0 avec
0 ≤ r 0 < n, alors r 0 est le reste de la division euclidienne de r 0 par n, ainsi r = r 0 .
D’où r est l’unique entier tel que r ∈ {0, 1, . . . , n − 1} et a ≡ r (mod n). 2

Corollaire 1.4.1 Soit n ∈ N∗ . Pour tout x ∈ Z, on note x la classe de x modulo n,

i.e., la classe d’équivalence de x modulo la congruence modulo n :
n o
x = y ∈ Z, y ≡ x (mod n) .

Z
On note par Z ou nZ
l’ensemble quotient de Z par la congruence modulo n, i.e.,

Z n o
Z= = x, x ∈ Z
nZ
Alors
Z n o n o
= r, 0 ≤ r ≤ n − 1 = 0, 1, . . . n − 1 .
nZ
De plus,  
Z
card = n.
nZ

Preuve On pose n o
F = r, 0 ≤ r ≤ n − 1 .

Si 0 ≤ r ≤ n − 1, alors r ∈ Z, donc r ∈ Z. Ainsi F ⊆ Z. D’autre part, si u ∈ Z, alors

il existe a ∈ Z tel que u = a. D’après la proposition 1.4.3, il existe un entier r tel que
0 ≤ r ≤ n − 1 et a ≡ r (mod n), donc

u = a = r ∈ F.

Ainsi Z ⊆ F . D’où n o
Z = F = r, 0 ≤ r ≤ n − 1 .

On pose [[1, n]] = {1, . . . , n} et on considère l’application f : [[1, n]] 7−→ Z définie
par :
f (k) = k − 1, ∀ k ∈ [[1, n]].
f est injective : Soient k, t ∈ [[1, n]] tels que f (k) = f (t), alors

k − 1 = t − 1, avec 0 ≤ k − 1 ≤ n − 1 et 0 ≤ t − 1 ≤ n − 1.

c Ali Ayad page 15

Chapitre 1 Arithmétique dans Z

Donc k − 1 = t − 1 d’après l’unicité dans la partie (2) de la proposition 1.4.3, ainsi k = t.

D’où f est injective.
f est surjective : Soit u ∈ Z, alors, d’après la partie (2) de la proposition 1.4.3, il existe
un entier r tel que u = r et 0 ≤ r ≤ n − 1. On pose k = r + 1, alors k ∈ [[1, n]] et

f (k) = k − 1 = r = u.

Ainsi f est surjective.

D’où f est bijective. Par conséquent, [[1, n]] est équipotent à Z. Ainsi Z est un ensemble
fini et card(Z) = n. 2

Remarque 1.4.1 Soit n ∈ N∗ et x, y ∈ Z.

1) x = y ⇔ x ≡ y (mod n).
2) x = 0 ⇔ n divise x.

Exemple 1.4.1 On considère l’ensemble quotient

Z n o
Z= = 0, 1, 2, 3, 4, 5 .
6Z
Z
Dans 6Z
, on a :
8 = 2 car 8 ≡ 2 (mod 6)
et
(−20) = 4 car − 20 ≡ 4 (mod 6).

Proposition 1.4.4 La congruence modulo n est compatible avec l’addition et la multipli-

cation dans Z, i.e., pour tous a, b, c, d ∈ Z et n ∈ N∗ ,
 
a ≡ b (mod n) a + c ≡ b + d (mod n)
si alors
c ≡ d (mod n) ac ≡ bd (mod n)

Preuve Si a ≡ b (mod n) et c ≡ d (mod n), alors il existe h, k ∈ Z tels que

a − b = nh et c − d = nk.

Donc
(a + c) − (b + d) = (a − b) + (c − d) = nh + nk = n(h + k).
Il s’ensuit que
a+c≡b+d (mod n).

c Ali Ayad page 16

Chapitre 1 Arithmétique dans Z

De plus,

ac − bd = ac − bc + bc − bd = (a − b)c + b(c − d)
= nhc + bnk = n(hc + bk),

avec hc + bk ∈ Z, donc n divise ac − bd, et par suite ac ≡ bd (mod n).

Autre méthode : Puisque a ≡ b (mod n), alors ac ≡ bc (mod n) d’après la propo-
sition 1.4.2. De même, puisque c ≡ d (mod n), alors bc ≡ bd (mod n), et donc
ac ≡ bd (mod n) par la transitivité de la congruence. 2

Corollaire 1.4.2 Soit n ∈ N∗ . Pour tous x, y ∈ Z

nZ
, on pose :

x+y =x+y et x y = xy.

Alors + et · sont deux lois de composition interne sur Z

nZ
.

Preuve Montrons que + et · ne dépendent pas du couple des répresentants (x, y) choisis.
En effet, si x = x0 et y = y 0 pour un autre couple (x0 , y 0 ) ∈ Z × Z, alors x ≡
x0 (mod n) et y ≡ y 0 (mod n). Mais la congruence modulo n est compatible avec
l’addition et la multiplication dans Z d’après la proposition 1.4.4, alors

x + y ≡ x0 + y 0 (mod n) et xy ≡ x0 y 0 (mod n).

Donc x + y = x0 + y 0 et xy = x0 y 0 dans Z
nZ
. Ainsi + et · sont deux lois de composition
Z
internes sur l’ensemble quotient nZ .2

 
Remarque 1.4.2 On verra dans le chapitre 3, que pour tout entier n ≥ 2, Z
nZ
, +, ·
est un anneau commutatif unitaire, appelé l’anneau des entiers modulo n.

1.5 Inversibles modulo un entier naturel n

Définition 1.5.1 Soit n ∈ N∗ . On dit qu’un entier a ∈ Z est inversible modulo n s’il
existe b ∈ Z tel que
ab ≡ 1 (mod n).
Ceci est équivalent à dire que l’équation de congruence ax ≡ 1 (mod n) admet une
solution dans Z.

c Ali Ayad page 17

Chapitre 1 Arithmétique dans Z

Proposition 1.5.1 Soit n ∈ N∗ et a ∈ Z. Si a est inversible modulo n, alors l’entier

b vérifiant ab ≡ 1 (mod n) est unique modulo n, i.e., si c est un autre entier vérifiant
ac ≡ 1 (mod n), alors
b ≡ c (mod n).
L’entier b est dit l’inverse de a modulo n, il est noté a−1 (mod n). De plus, b est
inversible modulo n et a est son inverse modulo n.

Preuve Soit b, c ∈ Z deux entiers vérifiant ab ≡ 1 (mod n) et ac ≡ 1 (mod n),

alors
b ≡ b.1 ≡ b(ac) ≡ (ba)c ≡ 1.c ≡ c (mod n).
Donc b est unique modulo n. Puisque ba ≡ ab ≡ 1 (mod n), alors b est inversible
modulo n et a est son inverse modulo n. 2

Remarque 1.5.1 Soit n ∈ N∗ et a ∈ Z. D’après la proposition 1.5.1, si l’équation de

congruence ax ≡ 1 (mod n) admet une solution dans Z, alors cette solution est unique
modulo n. En d’autres termes, l’existence d’une solution implique son unicité modulo n.

Exemple 1.5.1
1) L’inverse de 3 modulo 10 est 7 car 3 × 7 = 21 ≡ 1 (mod 10).
2) Comme 7 × 4 ≡ 1 (mod 27), alors l’inverse de 7 modulo 27 est 4 et l’inverse de
4 modulo 27 est 7.
3) L’inverse de 7 modulo 12 est 7 car 7 × 7 = 49 ≡ 1 (mod 12).

Proposition 1.5.2 Soit n ≥ 2 un entier naturel et a ∈ Z. Alors a est inversible modulo

n si et seulement si a est premier avec n.

Preuve
C.N. Comme a est inversible modulo n, alors il existe b ∈ Z tel que ab ≡ 1 (mod n),
donc il existe k ∈ Z tel que 1 − ab = kn, ainsi 1 = ba + kn avec b, k ∈ Z. On en
déduit, d’après le lemme de Bézout, que a et n sont premiers entre eux.
C.S. Comme a est premier avec n, alors il existe u, v ∈ Z tels que ua + vn = 1, donc
1 − ua = vn est divisible par n, et par suite ua ≡ 1 (mod n). Ainsi a est inversible
modulo n 2

Corollaire 1.5.1 Soit n ≥ 2 un entier naturel et a ∈ Z. L’équation de congruence

ax ≡ 1 (mod n) admet une solution dans Z (unique modulo n) si et seulement si a est
premier avec n.

c Ali Ayad page 18

Chapitre 1 Arithmétique dans Z

Preuve L’équation de congruence ax ≡ 1 (mod n) admet une solution dans Z si et

seulement si a est inversible modulo n, ceci est équivalent à que a est premier avec n
d’après la proposition 1.5.2. 2

Exemple 1.5.2
1) L’équation de congruence 3x ≡ 1 (mod 27) n’a pas de solutions dans Z car 3 ∧
27 = 3 6= 1.
2) L’équation de congruence 5x ≡ 1 (mod 27) admet de solutions dans Z car 5∧27 =
1. Comme
5(11) = 55 ≡ 1 (mod 27),
alors 11 est une solution de cette équation (unique modulo 27). Si x ∈ Z est une
solution quelconque de cette équation, alors x ≡ 11 (mod 27) et donc il existe
k ∈ Z tel que x = 11 + 27k.

1.6 L’équation de congruence ax ≡ b (mod n)

Proposition 1.6.1 Soit n ∈ N∗ et a, x, y ∈ Z.
Si ax ≡ ay (mod n) et a est premier avec n, alors x ≡ y (mod n).

Preuve Comme ax ≡ ay (mod n), alors n divise ax − ay = a(x − y). Mais

n est premier avec a, alors n divise x−y par le lemme de Gauss. Donc x ≡ y (mod n). 2

Proposition 1.6.2 Soit n ∈ N∗ et a, b ∈ Z. Si a est premier avec n, alors l’équation de

congruence linéaire ax ≡ b (mod n) admet une solution unique modulo n.

Preuve Puisque a est premier avec n, alors il existe u, v ∈ Z tels que ua + vn = 1,

alors bua + bvn = b et par suite a(ub) ≡ b (mod n), ce qui montre que x0 = ub est
une solution de l’équation de congruence ax ≡ b (mod n). D’autre part, si x, y ∈ Z
sont deux solutions de cette équation de congruence, alors

ax ≡ b (mod n) et ay ≡ b (mod n),

et donc ax ≡ ay (mod n). Mais a ∧ n = 1, alors x ≡ y (mod n) d’après la

proposition 1.6.1. 2

Corollaire 1.6.1 Soit a, b ∈ Z et p un nombre premier. Si p - a, alors l’équation de

congruence ax ≡ b (mod p) admet une solution unique modulo p.

c Ali Ayad page 19

Chapitre 1 Arithmétique dans Z

Preuve Puisque p est premier et p ne divise pas a, alors p est premier avec a, donc
l’équation de congruence ax ≡ b (mod p) admet une solution unique modulo p d’après
la proposition 1.6.2. 2

Exemple 1.6.1 Soit à résoudre, dans Z, l’équation de congruence

30x ≡ 19 (mod 113).

Par l’algorithme d’Euclide étendu, on obtient :

Restes Quotients y
113 − 49
30 3 13
23 1 10
7 3 3
2 3 1
1 2 0
0 − −

Donc 30 ∧ 113 = 1 et par suite l’équation admet une solution unique modulo 113. De
plus, on trouve 30(49) − 113(13) = 1, donc 30(49) ≡ 1 (mod 113) et par suite 49 est
l’inverse de 30 modulo 113. En multipliant l’équation par 49, qui est premier avec 113,
on obtient les équivalences :

30x ≡ 19 (mod 113) ⇔ 49(30x) ≡ (49)(19) (mod 113)

⇔ x ≡ 931 (mod 113)
⇔ x ≡ 27 (mod 113).

Ainsi l’unique solution modulo 113 de cette équation est x ≡ 27 (mod 113) et les
solutions dans Z sont les entiers 27 + 113k avec k ∈ Z. .

Théorème 1.6.1 Soit n ∈ N∗ , a, b ∈ Z et d = a ∧ n.

1) La congruence linéaire ax ≡ b (mod n) admet une solution dans Z si et seulement
si d divise b.
2) Si d divise b et si x0 ∈ Z est une solution particulière de cette congruence, alors
l’ensemble des solutions dans Z est donné par :
 
n
x = x0 + k où k ∈ Z.
d

Preuve

c Ali Ayad page 20

Chapitre 1 Arithmétique dans Z

1) C.N. Si x0 ∈ Z est une solution de cette congruence linéaire, alors ax0 ≡ b

(mod n), donc il existe k ∈ Z tel que ax0 + nk = b, i.e., (x0 , k) est une solution
de l’équation Diophantienne ax + ny = b, donc d divise b par le théorème 1.3.1.
C.S. Si d divise b, alors l’équation ax+ny = b admet une solution (x0 , y0 ) ∈ Z×Z
d’après le théorème 1.3.1, donc ax0 + ny0 = b, par suite ax0 ≡ b (mod n), i.e.,
x0 est une solution de la congruence ax ≡ b (mod n).
2) Supposons que d divise b et que x0 ∈ Z est une solution particulière de cette
congruence. Si x ∈ Z est une solution quelconque de cette congruence, alors ax ≡ b
(mod n) et ax0 ≡ b (mod n), donc ax ≡ ax0 (mod n), par suite il existe
h ∈ Z tel que
a(x − x0 ) = nh.
Comme d divise a et n, alors il existe a0 , n0 ∈ Z tels que a = da0 et n = dn0 ,
donc da0 (x − x0 ) = dn0 h. Comme d 6= 0, alors
a0 (x − x0 ) = n0 h.
Donc n0 divise a0 (x − x0 ), et comme n0 est premier avec a0 , alors n0 divise (x − x0 )
par le lemme de Gauss, ainsi il existe k ∈ Z tel que
 
0
n
x = x0 + kn = x0 + k .
d
 
Réciproquement, s’il existe k ∈ Z tel que x = x0 + k nd , alors
 
n
ax ≡ ax0 + ak (mod n)
d
 
a
≡ ax0 + nk (mod n)
d
≡ ax0 + nka0 (mod n)
≡ ax0 (mod n)
≡ b (mod n).
Donc x est une solution de cette congruence.

1.7 Le petit théorème de Fermat

Théorème 1.7.1 (Le petit théorème de Fermat)
Si p est un nombre premier et a ∈ Z, alors
ap ≡ a (mod p).
En particulier, si a est non divisible par p (i.e., a ∧ p = 1), alors
ap−1 ≡ 1 (mod p).

c Ali Ayad page 21

Chapitre 1 Arithmétique dans Z

1.8 Exercices
Exercice 1.1
Pour tout entier naturel n ∈ N∗ , on note par D(n) l’ensemble des diviseurs positifs de n,
i.e., n o
D(n) = d ∈ N∗ , tel que d | n .
On considère l’application σ : N∗ 7−→ N, définie, pour tout n ∈ N∗ , par :
X X
σ(n) = d= d.
d∈D(n) d|n

Un entier naturel n ∈ N∗ est dit un nombre parfait ou un nombre de Thabit ibn Qurra si
σ(n) = 2n, i.e., la somme de ses diviseurs positifs est 2n.
1) Trouver de nombres parfaits.
2) Soit r ∈ N tel que le nombre p = 2r+1 − 1 est premier. Montrer que l’entier
n = 2r p est parfait.

Exercice 1.2
1) Démontrer que, pour tout entier n ∈ N∗ , n! + 1 admet un diviseur premier p > n.
2) Déduire que l’ensemble des nombres premiers est infini.

Exercice 1.3
Tout entier de la forme Mn = 2n − 1 où n ∈ N∗ , s’appelle un nombre de Mersenne.
1) Montrer que si m, n ∈ N∗ tels que m divise n, alors Mm divise Mn .
2) Montrer que pour tout entier n ∈ N∗ , si Mn est premier, alors n est premier.

Exercice 1.4
n
Tout entier de la forme Fn = 22 + 1 où n ∈ N∗ , s’appelle un nombre de Fermat.
Démontrer que :
1) Tout entier n ∈ N∗ s’écrit, d’une manière unique, sous la forme n = 2r (2s + 1)
où r, s ∈ N.
2) Tout nombre premier de la forme 2m + 1 (où m ∈ N∗ ) est un nombre de Fermat
(i.e., m est une puissance de 2).

Exercice 1.5
Soit a, b, c ∈ Z \ {0} et m ∈ N∗ tels que m est premier avec a.
1) (a) Montrer que si a | b et b ∧ c = 1, alors a ∧ c = 1.

c Ali Ayad page 22

Chapitre 1 Arithmétique dans Z

(b) Montrer que a ∧ (mb) = a ∧ b.

2) Déduire que a ∨ (mb) = m(a ∨ b).

Exercice 1.6
Soit a, b, c ∈ Z \ {0} et m ∈ N∗ . Démontrer que :
1) a ∧ b = a ∧ (b + ka) pour tout k ∈ Z.
2) a ∧ b = 1 et a ∧ c = 1 si et seulement si a ∧ bc = 1.
a b
= a∧b



3) Si m divise a et m divise b, alors m ∧ m m
.
4) Si b ∧ c = 1, alors a ∧ (bc) = (a ∧ b)(a ∧ c).
5) a ∧ b = 1 si et seulement si a ∨ b = |ab|.

Exercice 1.7
Résoudre, dans Z × Z, les équations Diophantiennes suivantes :
1) 37x + 7y = 1.
2) 56x − 21y = 14.

Exercice 1.8
Soient x, y ∈ Z, a, n ∈ N∗ et d = a ∧ n.
n
1) Montrer que si ax ≡ ay (mod n), alors x ≡ y (mod d
).
2) En déduire que si ax ≡ ay (mod n) et a est premier avec n, alors x ≡ y
(mod n) (proposition 1.6.1).
3) Montrer que si p est un nombre premier tel que ax ≡ ay (mod p) et p ne divise
pas a, alors x ≡ y (mod p).

Exercice 1.9
Démontrer que pour tout n ∈ N,
1) 2 divise n(n + 1). 3) 6 divise n(n + 1)(n + 2).
2) 6 divise n(n − 1)(2n − 1). 4) 6 divise 5n3 + n.

Exercice 1.10
1) Démontrer que n3 + 2n est divisible par 3 pour tout n ∈ N∗ .
2) Démontrer que 52n − 1 est divisible par 24 pour tout n ∈ N.

Exercice 1.11

c Ali Ayad page 23

Chapitre 1 Arithmétique dans Z

1) Montrer que si 2 et 3 ne divisent pas n, alors 24 divise n2 + 23.

2) Montrer, par récurrence sur n, que 10n + 2 est divisible par 6 pour tout n ∈ N∗ .

Exercice 1.12
Démontrer que pour tout m, n ∈ N∗ ,
1) 11 divise 26n+3 + 32n+1 .
2) 7 divise 2n+2 + 32n+1 .
3) 5 × 43n+1 + 36m est divisible par 7.

Exercice 1.13
1) Montrer que pour tout n ∈ N, l’équation x2n − 2 = 3y n’a pas de solutions dans
Z × Z.
2) a) Montrer que, pour tout a ∈ Z, le reste de la division de a2 par 8 est 0, 1 ou 4.
b) Montrer que, si m est un entier congru à 3, 6 ou 7 modulo 8, alors l’équation
x2 + y 2 = m n’a pas de solutions dans Z × Z.

Exercice 1.14
Résoudre, dans Z, les congruences suivantes :
1) 3x ≡ 5 (mod 101). 2) 10x ≡ 4 (mod 21).
3) 5x ≡ 6 (mod 21). 4) 55x ≡ 35 (mod 75).
5) 42x ≡ 12 (mod 90). 6) 56x ≡ 35 (mod 75).

Exercice 1.15
Utiliser le petit théorème de Fermat pour trouver le reste de la division euclidienne de :
a) 63453 par 11. b) 31100 par 19.
c) 210000 par 29. d) 99999 par 31.

Exercice 1.16
Soient p et q deux nombres premiers impairs distincts tels que (p − 1) divise (q − 1).
Soit a ∈ Z tel que a ∧ p = 1 et a ∧ q = 1.
1) Appliquer le petit théorème de Fermat pour montrer que aq−1 ≡ 1 (mod p).
2) Déduire que aq−1 ≡ 1 (mod pq).

c Ali Ayad page 24