Congruences et anneau Z/nZ

L'heure qu'il sera dans $30$ heures, le jour de la semaine dans $100$ jours, le dernier chiffre de $3^{222}$ : dans chaque cas, seul compte un reste. La congruence est l'outil qui permet de calculer directement sur les restes, sans jamais écrire les grands nombres.

Définition. Soit $n \ge 2$. On dit que $a$ est congru à $b$ modulo $n$, et on note $a \equiv b \; [n]$, si $n$ divise $a - b$. De façon équivalente, $a$ et $b$ ont le même reste dans la division euclidienne par $n$. Exemple : $53 \equiv 3 \; [10]$ et $-17 \equiv 23 \; [40]$.

Compatibilité. Si $a \equiv a' \; [n]$ et $b \equiv b' \; [n]$, alors $a + b \equiv a' + b' \; [n]$ et $ab \equiv a'b' \; [n]$ ; donc aussi $a^{k} \equiv a'^{k} \; [n]$. On peut remplacer un nombre par n'importe quel nombre congru, au milieu d'un calcul, à condition de ne toucher qu'aux nombres qu'on additionne ou multiplie — jamais à un exposant.

L'anneau $\mathbb{Z}/n\mathbb{Z}$. La classe de $a$ est l'ensemble des entiers congrus à $a$ ; il y en a exactement $n$, une par reste possible $0, 1, \dots, n - 1$. La compatibilité permet d'additionner et de multiplier les classes : on obtient l'anneau $\mathbb{Z}/n\mathbb{Z}$. Dans cet anneau, on peut avoir $ab = 0$ sans $a = 0$ ni $b = 0$ : $4 \times 6 = 24 \equiv 0 \; [24]$.

Inversibilité. La classe de $a$ est inversible modulo $n$ s'il existe $u$ tel que $au \equiv 1 \; [n]$. Théorème :

la classe de $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a, n) = 1$.

Si $ua + vn = 1$ (Bézout), alors $ua \equiv 1 \; [n]$ : l'inverse se calcule par l'algorithme d'Euclide étendu. Réciproquement, si $au = 1 + kn$, tout diviseur commun de $a$ et $n$ divise $1$. Conséquence : quand $n = p$ est premier, toute classe non nulle est inversible, et $\mathbb{Z}/p\mathbb{Z}$ est un corps.

Ce qu'on n'a pas le droit de faire. Diviser une congruence par un entier non inversible. De $6x \equiv 6 \; [8]$ on ne tire pas $x \equiv 1 \; [8]$ : $x = 5$ convient aussi ($30 = 3 \times 8 + 6$). La division n'est permise que par un entier premier avec le module.

L'équation $ax \equiv c \; [n]$. Notons $d = \mathrm{pgcd}(a, n)$. L'équation équivaut à l'existence d'un entier $y$ avec $ax + ny = c$ ; le membre de gauche est toujours multiple de $d$, et Bézout montre que cette condition suffit.

• Si $d$ ne divise pas $c$ : aucune solution.
• Si $d$ divise $c$ : on divise tout par $d$ — les deux membres ET le module — pour obtenir $a'x \equiv c' \; [n']$ avec $a' = \dfrac{a}{d}$, $c' = \dfrac{c}{d}$, $n' = \dfrac{n}{d}$ et $\mathrm{pgcd}(a', n') = 1$. Cette équation a une solution unique $x_0$ modulo $n'$, et l'équation de départ a exactement $d$ solutions modulo $n$ : $x_0,\ x_0 + n',\ \dots,\ x_0 + (d - 1)n'$.

Exemple : $18x \equiv 12 \; [24]$. Ici $d = 6$, qui divise $12$. On obtient $3x \equiv 2 \; [4]$ ; l'inverse de $3$ modulo $4$ est $3$ ($9 \equiv 1$), donc $x \equiv 6 \equiv 2 \; [4]$. Modulo $24$ : six solutions, $2, 6, 10, 14, 18, 22$. En revanche $18x \equiv 15 \; [24]$ n'en a aucune, car $6$ ne divise pas $15$. Et $6x \equiv 6 \; [8]$ : $d = 2$, $3x \equiv 3 \; [4]$, $x \equiv 1 \; [4]$, soit deux solutions $1$ et $5$ modulo $8$.

Petit théorème de Fermat. Si $p$ est premier et ne divise pas $a$, alors $a^{p - 1} \equiv 1 \; [p]$. Pour calculer $a^{k}$ modulo $p$, on écrit la division euclidienne $k = q(p - 1) + r$ : alors $a^{k} \equiv a^{r} \; [p]$. On réduit l'exposant modulo $p - 1$, la base modulo $p$. Les deux hypothèses comptent : modulo $15$ (non premier), $2^{14} = 16\,384 \equiv 4 \; [15]$, pas $1$ ; et pour une base multiple de $p$, $a^{k} \equiv 0$.

Élévations au carré successives. Pour la petite puissance restante, on calcule $a^{2}, a^{4}, a^{8}, \dots$ modulo $p$ en réduisant à chaque étape, puis on multiplie les puissances qui composent $r$ en base $2$.

Théorème des restes chinois. Si $m_1$ et $m_2$ sont premiers entre eux, le système $x \equiv r_1 \; [m_1]$, $x \equiv r_2 \; [m_2]$ a une solution, unique modulo $m_1 m_2$. Méthode : on écrit $x = r_1 + m_1 k$, on reporte dans la seconde congruence, $m_1 k \equiv r_2 - r_1 \; [m_2]$, et on multiplie par l'inverse de $m_1$ modulo $m_2$. Exemple : $x \equiv 3 \; [10]$ et $x \equiv 4 \; [7]$. Alors $10k \equiv 1 \; [7]$, soit $3k \equiv 1 \; [7]$ ; l'inverse de $3$ modulo $7$ est $5$, donc $k \equiv 5 \; [7]$ et $x = 3 + 50 = 53$. Contrôle : $53 = 5 \times 10 + 3 = 7 \times 7 + 4$. $\checkmark$ Les autres solutions sont $53 + 70j$.

Énoncé.

1. Montrer que la classe de $7$ est inversible modulo $40$ et déterminer son inverse dans $\{0\,;\,1\,;\,\dots\,;\,39\}$.
2. Déterminer le reste de la division euclidienne de $3^{222}$ par $43$, sachant que $43$ est premier.

---

1. Euclide, puis Bézout. Algorithme d'Euclide sur $(40, 7)$ :

Le dernier reste non nul vaut $1$ : $\mathrm{pgcd}(7, 40) = 1$, la classe est inversible. On remonte :

Relation de Bézout : $(-17) \times 7 + 3 \times 40 = 1$, donc $(-17) \times 7 \equiv 1 \; [40]$. L'inverse est la classe de $-17$, dont le représentant dans $\{0\,;\,\dots\,;\,39\}$ est $-17 + 40 = 23$.

Contrôle : $7 \times 23 = 161 = 4 \times 40 + 1$. $\checkmark$

2. Fermat, puis carrés successifs. $43$ est premier et ne divise pas $3$ : $3^{42} \equiv 1 \; [43]$. Division de l'exposant par $p - 1 = 42$ : $222 = 5 \times 42 + 12$, donc

Carrés successifs, en réduisant à chaque fois : $3^{2} = 9$ ; $3^{4} = 81 \equiv 38$ ; $3^{8} \equiv 38^{2} = 1\,444 = 33 \times 43 + 25 \equiv 25$. Comme $12 = 8 + 4$ :

Le reste cherché est $4$.

Lecture. Euclide prouve l'inversibilité avant de calculer l'inverse ; Fermat réduit un exposant de trois chiffres à une puissance qu'on calcule à la main. Les deux calculs se vérifient en une ligne : un produit qui vaut $1$, une suite de restes tous inférieurs à $43$.

Figure (fig.math.prime-factor-tree, figure programmatique de la leçon de 3e sur les nombres premiers, réutilisée ici parce qu'elle fait voir un pgcd) : deux échelles de division côte à côte, $252 = 2^{2} \times 3^{2} \times 7$ à gauche, $180 = 2^{2} \times 3^{2} \times 5$ à droite ; les facteurs communs $2, 2, 3, 3$ sont hachurés, et le bilan encadre « facteurs communs : $2^{2} \times 3^{2} = 36$ ».

Pour cette leçon, lisez la figure comme la réponse à trois questions modulo $180$.

• $252$ est-il inversible modulo $180$ ? Non : $\mathrm{pgcd}(252, 180) = 36 \ne 1$. La partie hachurée, non vide, suffit à le dire. Seul un nombre dont l'échelle ne partage aucun facteur avec $2, 3, 5$ serait inversible modulo $180$ — par exemple $7$, ou $49$.
• Quand l'équation $252x \equiv c \; [180]$ a-t-elle des solutions ? Exactement quand $36$ divise $c$. Pour $c = 72$ : on divise tout par $36$, ce qui donne $7x \equiv 2 \; [5]$, soit $2x \equiv 2 \; [5]$ puisque $7 \equiv 2$, et $x \equiv 1 \; [5]$.
• Combien ? $36$ solutions modulo $180$ : $1, 6, 11, \dots, 176$. Le nombre de solutions est le nombre que la figure encadre.

La dernière ligne de la figure, $\dfrac{252}{180} = \dfrac{7}{5}$, est d'ailleurs exactement l'équation réduite : après division par le pgcd, le coefficient $7$ et le module $5$ sont premiers entre eux, et c'est pour cela que l'équation réduite a une solution unique.

Ce que la figure ne montre pas : le calcul de l'inverse lui-même (il faut l'algorithme d'Euclide étendu, pas la décomposition), et les puissances, pour lesquelles c'est la primalité du module qui compte.