Congruences

2.1 Définition

Définition. Soit $n$ un entier naturel, $n \geq 2$. Deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ s'ils ont le même reste dans la division euclidienne par $n$. On note $a \equiv b \;[n]$ et on lit « $a$ est congru à $b$ modulo $n$ ». On rencontre aussi les notations $a \equiv b \pmod n$ et $a \equiv b \;(n)$.

Théorème. $a \equiv b \;[n]$ si, et seulement si, $n$ divise $a - b$.

Démonstration. Écrivons $a = nq + r$ et $b = nq' + r'$ avec $0 \leq r < n$ et $0 \leq r' < n$. Alors $a - b = n(q - q') + (r - r')$, avec $-n < r - r' < n$.

• Si $r = r'$, alors $a - b = n(q - q')$ est un multiple de $n$.
• Si $n \mid a - b$, alors $n$ divise aussi $r - r' = (a - b) - n(q - q')$. Or le seul multiple de $n$ strictement compris entre $-n$ et $n$ est $0$ : donc $r = r'$.

Exemple 8.

• $23 \equiv 2 \;[7]$, car $23 = 7 \times 3 + 2$ ; de même $100 \equiv 2 \;[7]$, car $100 = 7 \times 14 + 2$.
• $-5 \equiv 2 \;[7]$, car $-5 - 2 = -7$ est un multiple de $7$.
• $2\,026 \equiv 0 \;[2]$ : un entier est pair si, et seulement si, il est congru à $0$ modulo $2$.

Conséquences.

• Si $r$ est le reste de la division euclidienne de $a$ par $n$, alors $a \equiv r \;[n]$. Tout entier est congru modulo $n$ à un, et un seul, des entiers $0$, $1$, …, $n - 1$ : son reste.
• $a \equiv 0 \;[n]$ si, et seulement si, $n$ divise $a$.
• Pour tous entiers $a$, $b$, $c$ : $a \equiv a \;[n]$ ; si $a \equiv b \;[n]$, alors $b \equiv a \;[n]$ ; si $a \equiv b \;[n]$ et $b \equiv c \;[n]$, alors $a \equiv c \;[n]$.

2.2 Congruences et opérations

Théorème. Si $a \equiv b \;[n]$ et $a' \equiv b' \;[n]$, alors :

• $a + a' \equiv b + b' \;[n]$ et $a - a' \equiv b - b' \;[n]$ ;
• $a\,a' \equiv b\,b' \;[n]$ ; en particulier $k\,a \equiv k\,b \;[n]$ pour tout entier $k$ ;
• $a^p \equiv b^p \;[n]$ pour tout entier naturel $p$.

Démonstration.

• $(a + a') - (b + b') = (a - b) + (a' - b')$ est la somme de deux multiples de $n$.
• $a\,a' - b\,b' = a\,(a' - b') + b'\,(a - b)$ est une combinaison de deux multiples de $n$.
• Pour les puissances, par récurrence sur $p$ : $a^0 = 1 \equiv 1 = b^0$, et si $a^p \equiv b^p \;[n]$, on multiplie membre à membre par $a \equiv b \;[n]$ pour obtenir $a^{p+1} \equiv b^{p+1} \;[n]$.

Méthode. Pour calculer un reste, on remplace chaque nombre par un nombre plus petit qui lui est congru, puis on calcule.

Exemple 9. Reste de $2\,026 \times 1\,999 + 100$ dans la division par $7$ : $2\,026 \equiv 3$, $1\,999 \equiv 4$ et $100 \equiv 2 \;[7]$, donc $2\,026 \times 1\,999 + 100 \equiv 3 \times 4 + 2 = 14 \equiv 0 \;[7].$ Ce nombre est un multiple de $7$.

Attention : on ne divise pas une congruence. $6 \equiv 16 \;[10]$, c'est-à-dire $2 \times 3 \equiv 2 \times 8 \;[10]$, mais $3 \not\equiv 8 \;[10]$.

2.3 Restes des puissances

Les restes des puissances successives d'un entier finissent par se répéter. Dès qu'une puissance est congrue à $1$, le cycle recommence.

Exemple 10. Les puissances de $2$ modulo $7$.

$k$	$1$	$2$	$3$	$4$	$5$	$6$
$2^k$ modulo $7$	$2$	$4$	$1$	$2$	$4$	$1$

Comme $2^3 = 8 \equiv 1 \;[7]$, on a $2^{3m} = (2^3)^m \equiv 1^m = 1 \;[7]$ pour tout entier naturel $m$. Pour $2^{100}$, on divise l'exposant par $3$ : $100 = 3 \times 33 + 1$, donc $2^{100} = (2^3)^{33} \times 2 \equiv 1 \times 2 = 2 \;[7].$ Le reste de $2^{100}$ dans la division par $7$ est $2$.

Exemple 11 (dernier chiffre). Le dernier chiffre d'un entier naturel est son reste dans la division par $10$. Les puissances de $7$ modulo $10$ valent $7$, $9$, $3$, $1$, puis le cycle recommence. Comme $2\,026 = 4 \times 506 + 2$, on a $7^{2\,026} = (7^4)^{506} \times 7^2 \equiv 49 \equiv 9 \;[10]$ : le dernier chiffre de $7^{2\,026}$ est $9$.

Exemple 12. Montrer que, pour tout entier naturel $n$, $3^{2n} - 2^n$ est divisible par $7$.

$3^{2n} = (3^2)^n = 9^n$ et $9 \equiv 2 \;[7]$, donc $9^n \equiv 2^n \;[7]$, c'est-à-dire $3^{2n} - 2^n \equiv 0 \;[7]$.

2.4 Applications : calendrier et critères de divisibilité

Le calendrier. Les jours de la semaine reviennent tous les $7$ jours : deux dates séparées par $N$ jours tombent le même jour de la semaine si, et seulement si, $N \equiv 0 \;[7]$. Pour savoir quel jour on sera dans $N$ jours, on cherche le reste de $N$ modulo $7$.

Exemple 13. Le 4 novembre 2026 est un mercredi. Quel jour de la semaine serons-nous $1\,000$ jours plus tard ?

$1\,000 = 7 \times 142 + 6$, donc $1\,000 \equiv 6 \;[7]$ : on avance de $6$ jours à partir du mercredi, et on tombe sur un mardi.

Critères de divisibilité. Un entier naturel s'écrit en base dix $N = a_k 10^k + \dots + a_1 10 + a_0$, où $a_0$, $a_1$, …, $a_k$ sont ses chiffres (voir la leçon 8).

• Comme $10 \equiv 1 \;[9]$, on a $10^i \equiv 1 \;[9]$, donc $N \equiv a_k + \dots + a_1 + a_0 \;[9]$ : un entier est congru modulo $9$ à la somme de ses chiffres. Il est divisible par $9$ si, et seulement si, cette somme l'est. Le même raisonnement vaut modulo $3$, car $10 \equiv 1 \;[3]$.
• Comme $10 \equiv -1 \;[11]$, on a $10^i \equiv (-1)^i \;[11]$, donc $N \equiv a_0 - a_1 + a_2 - \dots \;[11]$ : on alterne les signes en partant du chiffre des unités.

Exemple 14. Pour $N = 7\,654\,321$ : la somme des chiffres vaut $28$ et $28 \equiv 1 \;[9]$, donc $N \equiv 1 \;[9]$. La somme alternée vaut $1 - 2 + 3 - 4 + 5 - 6 + 7 = 4$, donc $N \equiv 4 \;[11]$.