Qu'est-ce que « Congruence » ?

Exemple 6.19 (La preuve par neuf)

La compatibilité avec $+$ et $\times$ est un procédé de vérification aussi vieux que le commerce. Comme $10 \equiv 1 \pmod 9$, tout entier est congru modulo $9$ à la somme de ses chiffres (démontré à l’Exercice 6.2). Pour vérifier l’affirmation $1234 \times 567 = 699\,678$ : les sommes des chiffres donnent $1234 \equiv 1$ et $567 \equiv 18 \equiv 0 \pmod 9$, donc le produit doit être $\equiv 1 \times 0 = 0$ ; et en effet $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. La vérification passe (et le produit est en fait correct). Si quelqu’un avait annoncé $699\,478$, la somme des chiffres $43 \equiv 7 \not\equiv 0$ le confondrait aussitôt. Le test est unilatéral — il attrape une erreur sauf si l’erreur est elle-même un multiple de $9$ — ce qui est exactement, en miniature, la leçon des pseudo-premiers de l’Exemple 6.24 : les vérifications par congruence réfutent, elles ne certifient pas.

Exemple 6.21 (Inverser $7$ modulo $26$)

Comme $\gcd(7, 26) = 1$, la classe de $7$ est inversible modulo $26$. Euclide étendu :

puis en remontant :

Donc $7 \times (-11) \equiv 1 \pmod{26}$, c’est-à-dire $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; vérification : $7 \times 15 = 105 = 4 \times 26 + 1$. Une fois l’inverse en main, toute congruence $7x \equiv c \pmod{26}$ se résout en une multiplication : $x \equiv 15c$. Cette inversion mécanique est le cheval de trait de l’arithmétique modulaire — et des protocoles à clé publique évoqués à la Remarque 6.27, où les modules ont des centaines de chiffres mais où l’algorithme est exactement celui-ci.

Exemple 6.22 (Quand le coefficient n’est pas inversible)

Résolvons $12x \equiv 8 \pmod{20}$. Ici $\gcd(12, 20) = 4$, donc $12$ n’est pas inversible modulo $20$ — mais l’équation reste traitable. La congruence dit que $20 \mid 12x - 8$ ; en divisant toute la relation par $4$ (diviseur des trois ingrédients), elle est équivalente à $5 \mid 3x - 2$, c’est-à-dire

Or $\gcd(3, 5) = 1$ et $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$), donc $x \equiv 4 \pmod 5$ : les solutions sont $x \equiv 4, 9, 14, 19 \pmod{20}$ — quatre classes modulo $20$, en accord avec le PGCD. (Si le second membre n’avait pas été divisible par $4$, par exemple $12x \equiv 6 \pmod{20}$, il n’y aurait aucune solution : le premier membre est toujours $\equiv 0 \pmod 4$.) Forme générale : $ax \equiv b \pmod n$ est résoluble si et seulement si $\gcd(a, n) \mid b$, et a alors exactement $\gcd(a, n)$ classes de solutions — on divise tout par le PGCD et on inverse.