Chapitre 3

Divisibilité et congruences

Sommaire
I Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 Définition et propriétés de la divisibilité dans Z . . . . . . . . . . . . . . . . . . . . . 1
2 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
II Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Tester la divisibilité d’un entier par un autre . . . . . . . . . . . . . . . . . . . . . . . 5
3 La preuve par 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
I Divisibilité
1 Définition et propriétés de la divisibilité dans Z
Définition(s).
Dire qu’un entier relatif b divise un entier relatif a signifie qu’il existe un entier relatif q tel que a = bq.
On dit alors que b est un diviseur de a ou que a est divisible par b ou encore que a est un multiple de b.

À noter.
On notera que tout entier relatif divise 0 et lui-même (0 = b ×0 et b = b ×1), que 0 ne divise que lui-même
(0 = 0 × q) et que les entiers relatifs 1 et −1 divisent tous les entiers relatifs (a = 1 × a et a = (−1) × (−a)).

Dans toute la suite du chapitre, sauf mention explicite du contaire, a, b et c désignent des entiers relatifs.

Proposition I.1 (À démontrer en exercice)

On a les équivalences suivantes :

b divise a ⇐⇒ −b divise a
⇐⇒ b divise −a
⇐⇒ −b divise −a.

Proposition I.2 (À démontrer en exercice)

Soit a 6= 0. Si b divise a, alors |b| É |a|.

Proposition I.3 (À démontrer en exercice)

Soit a 6= 0 et b 6= 0. Si b divise a et a divise b, alors |a| = |b|, c’est à dire a = b ou a = −b.

Proposition I.4 (À démontrer en exercice)

Soit a 6= 0 et b 6= 0. Si a divise b et b divise c, alors a divise c.

Proposition I.5 (À démontrer en exercice)

Soit c 6= 0. Si c divise a et b, alors c divise tout entier relatif de la forme au + bv avec u et v entiers relatifs.
En particulier, c divise a + b et a − b.

À noter.
En notant aZ l’ensemble des multiples de a, c’est à dire l’ensemble des entiers relatifs qui s’écrivent
a × k avec k dans Z, on peut démontrer l’équivalence suivante :

b divise a ⇐⇒ aZ ⊂ bZ.

2 Division euclidienne
Théorème (Division euclidienne)
Soit a et b deux entiers relatifs avec b > 0. Alors il existe un unique couple (q; r ) d’entiers relatifs tels que :

a = bq + r et 0 É r < b.

Démonstration.
On prouve d’abord l’existence d’un tel couple ³(q;´r ).
a
Les entiers a et b étant donnés, on pose q = E . Par définition, on a
b
a
q É < q + 1.
b

1
En multipliant par b > 0, on obtient
bq É a < bq + b.
En soustrayant bq, il en résulte que
0 É a − bq < b.
Finalement, en posant r = a − bq, on a bien

a = bq + r et 0 É r < b.

On prouve maintenant l’unicité.

On suppose l’existence de deux couples (q; r ) et (q ′ ; r ′ ) tels que :

a = bq + r, 0Ér <b et a = bq ′ + r ′ , 0 É r ′ < b.

Par différence, on obtient b(q − q ′ ) = r ′ − r , ce qui signifie que b divise r ′ − r . Or, puisque 0 É r < b et
0 É r ′ < b, on a
−b < −r É r ′ − r É r ′ < b
Ainsi, r ′ − r est un multiple de b appartenant à l’intervalle ] − b; b[. Le seul multiple de b appartenant
à l’intervalle ] − b; b[ étant 0, on en déduit que r ′ = r puis que q ′ = q. Le couple (q; r ) est bien le seul à
vérifier a = bq + r et 0 É r < b.

À noter.
Dans cette démonstration où a ∈ Z, on a utilisé la partie entière d’un nombre rationnel. Lorsque a ∈ N,
la démonstration de l’existence du couple (q; r ) peut se faire en se basant seulement sur une des des
deux propriétés intuitives suivantes de l’ensemble N des entiers naturels :

Tout sous-ensemble non vide de N possède un plus petit élément.

Tout sous-ensemble non vide et fini de N possède un plus grand élément.

Pour une démonstration utilisant la première propriété, voir le livre p. 84. Voici une autre démonstration
utilisant la deuxième propriété.
On considère le sous-ensemble A des entiers naturels dont le produit par b est inférieur ou égal à a :

A = {n ∈ N tels que bn É a}.

Le sous-ensemble A contient 0 (b ×0 É a). De plus, puisque b > 0, tout élément n de A vérifie n É bn É a.

Par conséquent, A est un sous-ensemble non vide et fini de N. On note q son plus grand élément et on
pose r = a − bq. Alors :


 q ∈ A =⇒ bq É a ou encore 0 É a − bq ,

 | {z }
r
a = bq + r et


 (q + 1) 6∈ A =⇒ a < b(q + 1) ou encore a − bq < b.
 | {z }
r

Définition(s).
Effectuer la division euclidienne d’un entier relatif a par un entier relatif b > 0, c’est trouver le couple
(q; r ) d’entiers relatifs tels que :
a = bq + r et 0 É r < b.
Dans la division euclidienne de a par b, on dit que a est le dividende, b le diviseur, q le quotient et r le
reste.

2
L’algorithme correspondant est le suivant :
³a ´
q ←− E
b .
r ←− a − bq

Il n’est pas difficile de généraliser le théorème de division euclidienne au cas d’un diviseur b entier relatif
non nul.

Théorème (Division euclidienne)

Soit a et b deux entiers relatifs avec b 6= 0. Alors il existe un unique couple (q; r ) d’entiers relatifs tels que :
a = bq + r et 0 É r < |b|.
Démonstration.
Il suffit de prouver l’existence du couple (q; r ) dans le cas b < 0, l’unicité se démontre alors comme dans
le cas b > 0.
On effectue la division euclidienne de a par |b| > 0 :
a = |b|q ′ + r ′ et 0 É r ′ < |b|.
En posant q = −q ′ et r = r ′ , on a bien
a = bq + r et 0 É r < |b|.
À noter.
Si b 6= 0, dire que b divise a, équivaut à dire que dans la division euclidienne de a par b, le reste r est nul.

Voici deux conséquences importantes du théorème de division euclidienne sur l’écriture d’un entier
relatif a.

Proposition I.6
Soit a et b deux entiers relatifs avec b > 0. Alors a s’écrit sous l’une des formes :
a = bq, a = bq + 1, a = bq + 2, ..., a = bq + (b − 1) avec q ∈ Z.
Proposition I.7 (Écriture d’un entier a > 0 en base b Ê 2)
Tout entier a > 0 s’écrit de manière unique sous la forme
a = an b n + · · · + a2 b 2 + a1 b + a0 ,
où n est un entier naturel, chaque ai un entier naturel strictement inférieur à b et an 6= 0.
Cette écriture s’appelle l’écriture de a en base b et les ai sont les chiffres de a en base b. On adopte la
convention d’écriture suivante : (
an . . . a2 a1 a0 si b = 10,
a= ¡ ¢
an . . . a2 a1 a0 b sinon.

II Congruences
1 Généralités
Dans toute la suite du chapitre, sauf mention explicite du contraire, n désigne un entier naturel tel que
n Ê 2 et a, b, c, a ′ , b ′ et c ′ des entiers relatifs.
Dans la division euclidienne de a par n, le reste r est un des entiers 0, 1, . . ., n −1 et d’après la proposition
I.6, les entiers relatifs peuvent être répartis entre n sous-ensembles dans lesquels tous les nombres ont
même reste dans la division euclidienne par n.

3
Définition(s).
Dire que a et b sont congrus modulo n signifie qu’ils ont le même reste dans la division euclidienne par
n. On écrit alors a ≡ b [n] ou a ≡ b (mod n) et on lit « a congru à b modulo n ».

À noter.
Puisque 0 = 0 × n + 0, dire que a ≡ 0 [n] signifie que n divise a.
Tout entier relatif a est congru modulo n à un, et un seul des entiers 0 ;1 ;. . . ;n − 1.
Il est immédiat de vérifier que la relation de congruence possède les trois propriétés suivantes :

a ≡ a [n] (Réflexivité) ;
a ≡ b [n] ⇐⇒ b ≡ a [n] (Symétrie) ;
a ≡ b [n] et b ≡ c [n] =⇒ a ≡ c [n] (Transitivité).

On dit que la relation de congruence modulo n est une relation d’équivalence sur Z. On appelle alors
classe d’équivalence de l’entier relatif k, et on note k̇, l’ensemble de tous les entiers relatifs congrus à k
modulo n, c’est à dire
k̇ = {k ′ ∈ Z tels que k ′ ≡ k [n]}.
L’ensemble des classes d’équivalence est appelé ensemble quotient de Z par la relation de congruence
modulo n et noté Z/nZ. D’après ce qui précède, on peut affirmer que
˙ 1}.
Z/nZ = {0̇, 1̇, 2̇, . . . , n −

Théorème
Dire que a ≡ b [n] équivaut à dire que n divise a − b.

Démonstration.
On suppose que a ≡ b [n]. Alors :

a = nq + r et b = nq ′ + r avec q ∈ Z, q ′ ∈ Z et 0 É r < n, donc a − b = n(q − q ′ ).

Réciproquement, on suppose que n divise a − b. Il existe donc un entier relatif q tel que a − b = nq. On
effectue alors la division euclidienne de b par n :

b = nq ′ + r ′ avec q ′ ∈ Z et 0 É r ′ < n.

Par addition, on obtient :

a = (a − b) + b
= nq + nq ′ + r ′ avec 0 É r ′ < n.
= n(q + q ′ ) + r ′
Par unicité du quotient et du reste dans la division euclidienne de a par n, cette affirmation prouve que
r ′ est le reste dans la division euclidienne de a par n.

Le théorème suivant montre que la relation de congruence est compatible avec les opérations usuelles.

Théorème (Règles de calcul sur les congruences.)

Si
a ≡ b [n] et a ′ ≡ b ′ [n],
alors :

a + a ′ ≡ b + b ′ [n], −a ′ ≡ −b ′ [n] et a − a ′ ≡ b − b ′ [n];

aa ′ ≡ bb ′ [n] et pour tout entier naturel p Ê 1, a p ≡ b p [n].

4
Démonstration (Partielle).
Par hypothèse, il existe des entiers relatifs q et q ′ tels que :

a − b = nq et a ′ − b ′ = nq ′ .

Il en découle que :

(a + a ′ ) − (b + b ′ ) = n(q + q ′ )

et

−a ′ − (−b ′ ) = n × (−q ′ ).

Les deux premières propriétés sont alors démontrées et ont pour conséquence immédiate la troisième.
La quatrième propriété s’obtient en écrivant :

aa ′ = (b + nq)(b ′ + nq ′ )
= bb ′ + bnq ′ + nqb ′ + nqnq ′
= bb ′ + n(bq ′ + qb ′ + nq q ′ ).

La démonstration par récurrence sur l’entier p Ê 1 de la dernière propriété est laissée à titre d’exercice.

À noter.
Il en découle que si a ≡ b [n], alors :

a + c ≡ b + c [n], a − c ≡ b − c [n] et ac ≡ bc [n].

Ce théorème permet de définir des opérations + et × sur l’ensemble quotient Z/nZ en posant, pour tous
ȧ et ḃ de Z/nZ :
˙ ˙
ȧ + ḃ = a + b et ȧ × ḃ = a × b.
Muni de ces opérations, Z/nZ est un anneau commutatif qui possède des règles de calcul différentes de
celles auxquelles nous sommes habitués. Par exemple, le produit de deux éléments non nuls de Z/nZ
peut être nul. Il convient donc de manipuler Z/nZ avec prudence !

2 Tester la divisibilité d’un entier par un autre

Il existe des moyens pour déterminer si un entier b divise un entier a sans avoir à effectuer la division de
a par b. Ces moyens sont appelés critères de divisibilité. Certains ne nécessitent que d’observer l’entier
à tester, voire une partie de celui-ci, d’autres nécessitent un calcul.

Proposition II.1 (Critères de divisibilité)

Un entier naturel est divisible par 2 si, et seulement si son chiffre des unités est 0, 2, 4, 6 ou 8.
Un entier naturel est divisible par 5 si, et seulement si son chiffre des unités est 0 ou 5.
Un entier naturel est divisible par 10 si, et seulement si son chiffre des unités est 0.

Un entier naturel est divisible par 3 si, et seulement si la somme des chiffres dans son écriture décimale est
divisible par 3.
Un entier naturel est divisible par 9 si, et seulement si la somme des chiffres dans son écriture décimale est
divisible par 9.
Un entier naturel est divisible par 11 si, et seulement si la somme alternée des chiffres dans son écriture
décimale est divisible par 11.

5
Démonstration.
Tout entier naturel a > 0 s’écrit de manière unique sous la forme

a = an × 10n + · · · + a2 × 102 + a1 × 10 + a0 ,

où n est un entier naturel, chaque ai un entier naturel strictement inférieur à 10 et an 6= 0.

Pour conclure, il suffit de noter que

10 ≡ 1 [3], 10 ≡ 1 [9] et 10 ≡ (−1) [11]

puis d’appliquer les règles de calcul sur les congruences à l’écriture de a en base 10 (écriture décimale).

À noter.
D’autres critères de divisibilité découlent de propriétés plus générales qui sont plus délicates à prouver.
L’itération d’un critère de divisibilité par un nombre b > 0 sur un nombre a > 0 jusqu’à obtenir un
nombre 0 É r < b donne le reste dans la division euclidienne de a par b.

Exemple(s).
Démontrer que 11 divise 1742772625 − 1.
Tout d’abord, on a :
7 − 7 + 2 − 4 + 7 − 1 = 4 =⇒ 174277 ≡ 4 [11]
On remarque alors que :

42 ≡ 5 [11] =⇒ 44 ≡ 3 [11]
=⇒ 45 ≡ 1 [11].

Par conséquent :

1742772625 ≡ 42625 [11] et 4 2625 525

| {z } ≡ 1 [11] =⇒ 1742772625 ≡ 1 [11].
(45 )525

3 La preuve par 9
Une autre application des règles de calcul sur les congruences est la preuve par 9 qui permettait, avant
l’avènement des calculatrices de détecter d’éventuelles erreurs dans une addition, une soustraction ou
une multiplication.
S’agissant, par exemple, de détecter d’éventuelles erreurs dans la multiplication

687952 | {z } = 5644520705776
| {z } × 8204963 | {z },
a b c

on calcule modulo 9 les valeurs de a et de b. On trouve alors que

a ≡ 1 [9] et b ≡ 5 [9].

D’après les règles de calcul sur les congruences, on en déduit que a×b ≡ 5 [9]. On calcule ensuite modulo
9 la valeur de c. Ici, c ≡ 4 [9]. Il y a donc au moins une erreur !

À noter.
Attention, si la preuve donne une congruence incorrecte, on est certain que l’opération est fausse, mais
si la preuve donne la bonne congruence, l’opération n’est pas forcément juste. En effet, le résultat peut
différer de la valeur exacte d’un multiple de 9. Ainsi, la multiplication 45×17 = 855 est fausse malgré une
preuve par 9 positive.