Divisibilité et congruences
Quel jour de la semaine serons-nous dans 1 000 jours ? Quel est le dernier chiffre de $7^{2026}$ ? Comment un code-barres détecte-t-il une erreur de saisie ? On ne s'intéresse qu'aux restes : c'est le calcul modulaire, l'arithmétique de l'horloge.
- Utiliser la divisibilité dans $\mathbb{Z}$ et ses propriétés
- Effectuer une division euclidienne, y compris d'un entier négatif
- Calculer avec des congruences, trouver le reste d'une puissance
- Établir et utiliser des critères de divisibilité, des clés de contrôle
Cours
1. Divisibilité dans ℤ
Soit $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$, et on note $a \mid b$, s'il existe un entier $k$ tel que $b = ka$. On dit aussi que $b$ est un multiple de $a$, ou que $a$ est un diviseur de $b$.
Exemples : $3 \mid -12$ ; $-5 \mid 35$ ; tout entier divise $0$ ; $1$ et $-1$ divisent tout entier.
- Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
- Combinaisons linéaires : si $a \mid b$ et $a \mid c$, alors $a \mid bu + cv$ pour tous entiers $u$ et $v$.
- Si $a \mid b$ et $b \neq 0$, alors $|a| \leqslant |b|$ : un entier non nul a un nombre fini de diviseurs.
Si $a \mid b$ et $a \mid c$, alors $a \mid bu + cv$ pour tous $u, v \in \mathbb{Z}$.
Il existe des entiers $k$ et $k'$ tels que $b = ka$ et $c = k'a$. Alors $bu + cv = kau + k'av = (ku + k'v)a$, et $ku + k'v$ est un entier. $\blacksquare$
Déterminer les entiers $n$ tels que $n + 5$ divise $2n + 3$. Si $n + 5 \mid 2n + 3$, comme $n + 5 \mid 2(n + 5)$, on a $n + 5 \mid 2(n + 5) - (2n + 3) = 7$. Donc $n + 5 \in \{-7, -1, 1, 7\}$, soit $n \in \{-12, -6, -4, 2\}$. On vérifie que ces quatre valeurs conviennent.
2. Division euclidienne
Soit $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$. Il existe un unique couple d'entiers $(q\,;\,r)$ tel que $$a = bq + r \quad\text{et}\quad 0 \leqslant r < b.$$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
Preuve du théorème.
Existence. Soit $q$ le plus grand entier tel que $bq \leqslant a$ (c'est la partie entière de $\frac ab$), et $r = a - bq$. Alors $r \geqslant 0$, et $b(q + 1) > a$ donne $r < b$.
Unicité. Si $a = bq + r = bq' + r'$ avec $0 \leqslant r, r' < b$, alors $b(q - q') = r' - r$. Or $-b < r' - r < b$, donc $|q - q'| < 1$ : $q = q'$ puis $r = r'$. $\blacksquare$
Pour un dividende négatif, le reste doit rester positif : $-17 = 5 \times (-4) + 3$ (et non $5 \times (-3) - 2$). En Python, a // b et a % b donnent bien le quotient et le reste euclidiens, même si $a < 0$.
3. Congruences
Soit $n \geqslant 2$. Deux entiers $a$ et $b$ sont congrus modulo $n$ si $n$ divise $a - b$. On note $a \equiv b\ [n]$ (ou $a \equiv b \pmod n$).
De façon équivalente : $a$ et $b$ ont le même reste dans la division euclidienne par $n$. En particulier, tout entier est congru modulo $n$ à son reste, et $a \equiv 0\ [n] \iff n \mid a$.
$29 \equiv 5\ [12]$ : 29 heures après minuit, il est 5 h. $\;-1 \equiv 6\ [7]$ : hier, c'était le même jour de la semaine que dans 6 jours.
Si $a \equiv b\ [n]$ et $c \equiv d\ [n]$, alors : $\;a + c \equiv b + d\ [n]$, $\;ac \equiv bd\ [n]$, et $a^k \equiv b^k\ [n]$ pour tout entier naturel $k$.
Preuve pour le produit, puis les puissances.
$ac - bd = ac - ad + ad - bd = a(c - d) + d(a - b)$. Or $n \mid c - d$ et $n \mid a - b$ : $n$ divise cette combinaison linéaire, donc $ac \equiv bd\ [n]$.
Pour les puissances, récurrence sur $k$ : $a^0 = b^0 = 1$ ; si $a^k \equiv b^k$, alors $a^{k+1} = a^k \times a \equiv b^k \times b = b^{k+1}$ par le produit. $\blacksquare$
On ne peut pas « simplifier » une congruence : $2 \times 3 \equiv 2 \times 8\ [10]$ mais $3 \not\equiv 8\ [10]$. On verra que l'on peut diviser par $a$ lorsque $a$ est premier avec $n$.
Reste de $3^{2026}$ dans la division par 7. On cherche une puissance de 3 congrue à 1 : $3^1 \equiv 3$, $3^2 \equiv 2$, $3^3 \equiv 6$, $3^4 \equiv 4$, $3^5 \equiv 5$, $3^6 \equiv 1\ [7]$.
$2026 = 6 \times 337 + 4$, donc $3^{2026} = \left(3^6\right)^{337} \times 3^4 \equiv 1^{337} \times 81 \equiv 4\ [7]$. Le reste est 4.
Montrons que $n^2 + n + 1$ n'est jamais divisible par 5. On étudie tous les restes possibles de $n$ modulo 5 :
| $n \equiv$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $n^2 + n + 1 \equiv$ | 1 | 3 | 2 | 3 | 1 |
Le reste n'est jamais 0 : $5 \nmid n^2 + n + 1$ pour tout entier $n$.
$3x \equiv 2\ [7]$. Dans la table de multiplication modulo 7, $3 \times 5 = 15 \equiv 1$ : 5 est un inverse de 3 modulo 7. En multipliant par 5 : $x \equiv 10 \equiv 3\ [7]$. Les solutions sont les entiers $x = 3 + 7k$, $k \in \mathbb{Z}$.
4. Critères de divisibilité et clés de contrôle
Soit $N = \overline{a_ka_{k-1}\dots a_1a_0} = \sum a_j10^j$ l'écriture décimale d'un entier.
- $10 \equiv 1\ [9]$ (et $[3]$) donc $N \equiv a_0 + a_1 + \dots + a_k$ : $N$ est divisible par 9 (par 3) si et seulement si la somme de ses chiffres l'est.
- $10 \equiv -1\ [11]$ donc $N \equiv a_0 - a_1 + a_2 - \dots\ [11]$ : critère de divisibilité par 11.
- $100 \equiv 0\ [4]$ donc $N \equiv \overline{a_1a_0}\ [4]$ : on regarde les deux derniers chiffres.
Un entier est divisible par 9 si et seulement si la somme de ses chiffres l'est.
Comme $10 \equiv 1\ [9]$, on a $10^j \equiv 1^j = 1\ [9]$ pour tout $j$ (compatibilité avec les puissances). Donc $N = \sum a_j10^j \equiv \sum a_j\ [9]$ (compatibilité avec la somme et le produit). $N$ et la somme de ses chiffres ont le même reste modulo 9 ; en particulier l'un est divisible par 9 si et seulement si l'autre l'est. $\blacksquare$
Les numéros de sécurité sociale, codes-barres, ISBN ou RIB se terminent par une clé de contrôle calculée avec des congruences : elle permet de détecter la plupart des erreurs de saisie.
La notation $a \equiv b\ [n]$ est due à Gauss, dans ses Disquisitiones arithmeticae (1801), écrites à 24 ans. Les calculs de calendrier (date de Pâques, jour de la semaine d'une date) sont des applications anciennes du calcul modulaire.
Mini-jeux
Exercices
Effectuer la division euclidienne de $2\,026$ par $17$, puis de $-2\,026$ par $17$.
Reste de la seconde :
$2\,026 = 17 \times 119 + 3$. $\;-2\,026 = 17 \times (-120) + 14$ (car $17 \times 120 = 2\,040$ et $-2\,026 + 2\,040 = 14$).
Déterminer le reste de la division de $5^{100}$ par 3, puis de $2^{2026}$ par 7.
Reste de $2^{2026}$ par 7 :
$5 \equiv -1\ [3]$ donc $5^{100} \equiv (-1)^{100} = 1\ [3]$. $\;2^3 = 8 \equiv 1\ [7]$ et $2026 = 3 \times 675 + 1$, donc $2^{2026} \equiv 2\ [7]$.
Montrer à l'aide d'un tableau de congruences que $n(n + 1)(n + 2)$ est divisible par 3 pour tout entier $n$.
Si $n \equiv 0$, le facteur $n$ est divisible par 3 ; si $n \equiv 1$, c'est $n + 2 \equiv 0$ ; si $n \equiv 2$, c'est $n + 1 \equiv 0\ [3]$. Dans tous les cas le produit est $\equiv 0\ [3]$.
Déterminer les entiers naturels $n$ tels que $2^n - 1$ soit divisible par 7.
Les restes de $2^n$ modulo 7 sont $1, 2, 4, 1, 2, 4, \dots$ (période 3 car $2^3 \equiv 1$). Donc $2^n \equiv 1\ [7] \iff n$ est un multiple de 3.
Résoudre $5x \equiv 3\ [12]$.
$5 \times 5 = 25 \equiv 1\ [12]$ : 5 est son propre inverse modulo 12. En multipliant par 5 : $x \equiv 15 \equiv 3\ [12]$. Réciproquement $5 \times 3 = 15 \equiv 3$. Solutions : $x = 3 + 12k$.
Sans calculatrice, $123\,456\,789$ est-il divisible par 11 ? Et $918\,082$ ?
Somme alternée en partant des unités : $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ : non. Pour $918\,082$ : $2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0\ [11]$ : oui ($918\,082 = 11 \times 83\,462$).
Montrer que pour tout entier $n$, $n^5 - n$ est divisible par 5, puis par 30.
Modulo 5 : si $n \equiv 0, 1, 2, 3, 4$, alors $n^5 \equiv 0, 1, 32, 243, 1024 \equiv 0, 1, 2, 3, 4$ : toujours $n^5 \equiv n$. De même $n^5 - n = n(n - 1)(n + 1)(n^2 + 1)$ contient trois entiers consécutifs, donc est divisible par 2 et par 3. Divisible par 2, 3 et 5, il est divisible par 30 (on le justifiera avec le théorème de Gauss).
La clé d'un code EAN-13 est choisie pour que $S = a_1 + 3a_2 + a_3 + 3a_4 + \dots + 3a_{12} + a_{13} \equiv 0\ [10]$. (a) Montrer qu'une erreur sur un seul chiffre est toujours détectée. (b) Montrer que l'échange de deux chiffres voisins $a$ et $b$ n'est pas détecté si et seulement si $|a - b| = 5$.
(a) Si un chiffre $a$ est remplacé par $a' \neq a$, $S$ change de $c(a' - a)$ avec $c = 1$ ou $3$. Comme $0 < |a' - a| \leqslant 9$ et que 1 et 3 sont inversibles modulo 10, $c(a' - a) \not\equiv 0\ [10]$ : la nouvelle somme n'est plus multiple de 10.
(b) L'échange de $a$ (poids 1) et $b$ (poids 3) change $S$ de $(b + 3a) - (a + 3b) = 2(a - b)$. Ce changement passe inaperçu $\iff 10 \mid 2(a - b) \iff 5 \mid a - b \iff |a - b| \in \{0, 5\}$ ; pour deux chiffres distincts, $|a - b| = 5$.