Arithmétique : divisibilité et congruences

Le numéro d’une carte bancaire, la clé d’un numéro de Sécurité sociale, le chiffrement de tes messages : tout ça repose sur l’arithmétique des entiers. En maths expertes, tu retrouves les nombres les plus familiers qui soient — mais avec un outil neuf et redoutable : les congruences, une façon de calculer uniquement sur les restes. Tout le chapitre tient dans une idée : quand on divise, ce qui compte souvent, ce n’est pas le quotient… c’est le reste.

La divisibilité dans ℤ

Soient $a$ et $b$ deux entiers relatifs. On dit que $b$ divise $a$ (noté $b \mid a$) s’il existe un entier $k$ tel que $a = kb$. On dit aussi que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$. Exemple : $7 \mid 91$ car $91 = 7 \times 13$.

• Tout entier non nul a un nombre fini de diviseurs (ils sont compris entre $-|a|$ et $|a|$) mais une infinité de multiples.
• Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
• Combinaisons linéaires : si $d \mid a$ et $d \mid b$, alors $d$ divise $au + bv$ pour tous entiers $u$ et $v$ — en particulier $a + b$ et $a - b$.

La division euclidienne

Pour tout entier $a \in \mathbb{Z}$ et tout entier naturel $b \in \mathbb{N}^*$, il existe un unique couple $(q\,;\,r)$ d’entiers tel que :

$a = bq + r \qquad \text{avec} \qquad 0 \leq r < b$

$q$ est le quotient, $r$ le reste. Exemple : $247 = 17 \times 14 + 9$, donc la division euclidienne de $247$ par $17$ a pour quotient $14$ et pour reste $9$. Et $b \mid a$ si, et seulement si, le reste est nul.

Les congruences modulo n

Soit $n \geq 2$ un entier. Deux entiers $a$ et $b$ sont congrus modulo $n$, noté $a \equiv b \pmod{n}$ (ou $a \equiv b\ [n]$), lorsque $n$ divise $a - b$ — autrement dit lorsque $a$ et $b$ ont le même reste dans la division euclidienne par $n$. Exemple : $25 \equiv 4 \pmod{7}$ car $25 - 4 = 21 = 3 \times 7$. Tout entier est ainsi congru modulo $n$ à un unique reste compris entre $0$ et $n - 1$.

C’est toute la puissance du chapitre : pour connaître le reste d’un calcul énorme, on remplace chaque nombre par son reste avant de calculer. Le reste de $25 \times 32$ modulo $7$ ? $25 \equiv 4$ et $32 \equiv 4 \pmod{7}$, donc $25 \times 32 \equiv 16 \equiv 2 \pmod{7}$. Aucune grosse multiplication.

Trois applications à connaître

• Critères de divisibilité : comme $10 \equiv 1 \pmod{9}$, on a $10^k \equiv 1 \pmod 9$ pour tout $k$, donc tout entier est congru modulo $9$ à la somme de ses chiffres. D’où le critère : divisible par $9$ (ou par $3$) si, et seulement si, la somme de ses chiffres l’est. Avec $10 \equiv -1 \pmod{11}$, on obtient de même le critère par $11$ (somme alternée des chiffres).
• Chiffre des unités : c’est le reste modulo $10$. Le chiffre des unités de $7^{2026}$ ? Les puissances de $7$ finissent par $7, 9, 3, 1, 7, 9, \ldots$ — un cycle de longueur $4$.
• Restes de grandes puissances : cherche une petite puissance congrue à $1$ (ou à $-1$). Pour $2^{100}$ modulo $7$ : $2^3 = 8 \equiv 1 \pmod 7$, et $100 = 3 \times 33 + 1$, donc $2^{100} = (2^3)^{33} \times 2 \equiv 1^{33} \times 2 \equiv 2 \pmod 7$.

Résoudre une congruence ax ≡ b (mod n)

Pas de formule magique en général : la méthode robuste est le tableau de restes. Pour résoudre $3x \equiv 5 \pmod 7$, on teste les $7$ restes possibles de $x$ :

$x \equiv$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3x \equiv$	$0$	$3$	$6$	$2$	$5$	$1$	$4$

Seul $x \equiv 4 \pmod 7$ convient : les solutions sont les entiers de la forme $4 + 7k$, $k \in \mathbb{Z}$. (Au chapitre suivant, le théorème de Bézout fournira une méthode plus directe : multiplier par un inverse de $a$ modulo $n$.)

Les pièges classiques