L'essentiel à connaître
Deux entiers $a$ et $b$ sont congrus modulo $n$ quand $n$ divise $a - b$ : on écrit $a \equiv b \ [n]$, parfois $a \equiv b \pmod{n}$. Par exemple, $23 \equiv 2 \ [7]$ car $23 - 2 = 3 \times 7$. L'anneau $\mathbb{Z}/n\mathbb{Z}$ réunit les $n$ classes $\bar 0, \bar 1, \dots, \overline{n-1}$ : on y calcule comme dans $\mathbb{Z}$, puis on remplace le résultat par son reste dans la division par $n$.
Les congruences s'additionnent, se multiplient et s'élèvent à une puissance membre à membre. Simplifier par un entier $c$, en revanche, n'est permis que si $c$ est premier avec $n$, c'est-à-dire si leur PGCD, noté $c \wedge n$, vaut 1.
Règle : la classe $\bar a$ est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si $a \wedge n = 1$ ; une relation de Bézout $au + nv = 1$ donne alors l'inverse $\bar u$. Les mêmes classes sont les générateurs du groupe additif $(\mathbb{Z}/n\mathbb{Z}, +)$. Leur nombre est l'indicatrice d'Euler $\varphi(n)$, avec $\varphi(p^k) = p^k - p^{k-1}$ pour $p$ premier et $k \geq 1$, et $\varphi(mn) = \varphi(m)\varphi(n)$ si $m \wedge n = 1$. Ainsi, $\mathbb{Z}/n\mathbb{Z}$ est un corps si et seulement si $n$ est premier.
Si $n \geq 2$ n'est pas premier, l'anneau a des diviseurs de zéro, des classes non nulles dont le produit est nul : $\bar 2 \times \bar 3 = \bar 0$ dans $\mathbb{Z}/6\mathbb{Z}$. L'équation $ax \equiv b \ [n]$ a des solutions si et seulement si $d = a \wedge n$ divise $b$ ; on divise alors tout par $d$, modulo compris, et on obtient $d$ solutions modulo $n$.
À retenir : si $p$ est premier et ne divise pas $a$, alors $a^{p-1} \equiv 1 \ [p]$ (petit théorème de Fermat), mais la réciproque est fausse. Si $a \wedge n = 1$, alors $a^{\varphi(n)} \equiv 1 \ [n]$ (théorème d'Euler). L'ordre d'un inversible $\bar a$, le plus petit entier $k \geq 1$ tel que $a^k \equiv 1 \ [n]$, divise $\varphi(n)$.
Théorème chinois : si $m \wedge n = 1$, l'anneau $\mathbb{Z}/mn\mathbb{Z}$ est isomorphe à $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$. Un système $x \equiv a \ [m]$ et $x \equiv b \ [n]$ a donc une seule solution modulo $mn$.
L'anneau $\mathbb{Z}/n\mathbb{Z}$, l'indicatrice d'Euler et le théorème chinois figurent au programme de mathématiques des classes MP et MPI (2021).
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Que signifie $a \equiv b \ [n]$ ?
Réponse : C. Par définition, $a - b$ est un multiple de $n$, comme $23 - 2 = 3 \times 7$. Le piège A inverse les rôles : $21$ ne divise pas $7$, et pourtant $23 \equiv 2 \ [7]$.
Question 2 : Quelle est la classe de $-23$ dans $\mathbb{Z}/7\mathbb{Z}$ ?
Réponse : D. On écrit $-23 = (-4) \times 7 + 5$, avec un reste entre 0 et 6, donc $\overline{-23} = \bar 5$. Le piège $\bar 2$ oublie le signe : la classe de $-23$ est l'opposée de $\bar 2$, c'est-à-dire $\bar 5$.
Question 3 : Quel est le chiffre des unités de $7^{102}$ ?
Réponse : A. Le chiffre des unités est le reste modulo 10 : $7^2 = 49 \equiv 9$ et $7^4 \equiv 9^2 = 81 \equiv 1 \ [10]$. Avec $102 = 4 \times 25 + 2$, on obtient $7^{102} \equiv 7^2 \equiv 9 \ [10]$. Le piège 1 traite 102 comme un multiple de 4.
Question 4 : Quels sont les éléments inversibles de $\mathbb{Z}/10\mathbb{Z}$ ?
Réponse : B. Il faut et il suffit que $a \wedge 10 = 1$, ce qui laisse 1, 3, 7 et 9 ; par exemple $\bar 3 \times \bar 7 = \overline{21} = \bar 1$. Le piège C garde $\bar 5$, mais un multiple de 5 vaut 0 ou 5 modulo 10, jamais 1.
Question 5 : Pour $n \geq 2$, l'anneau $\mathbb{Z}/n\mathbb{Z}$ est un corps si et seulement si :
Réponse : A. Un corps demande que chaque classe non nulle soit inversible, donc que chaque entier de 1 à $n - 1$ soit premier avec $n$ : c'est dire que $n$ est premier. Le piège C échoue dès $n = 4$, où $\bar 2 \times \bar 2 = \bar 0$.
Question 6 : Quel est l'inverse de $\bar 7$ dans $\mathbb{Z}/26\mathbb{Z}$ ?
Réponse : C. L'algorithme d'Euclide donne la relation de Bézout $3 \times 26 - 11 \times 7 = 1$, donc l'inverse est $\overline{-11} = \overline{15}$ ; on vérifie que $7 \times 15 = 105 = 4 \times 26 + 1$. Le piège $\overline{11}$ oublie le signe : $7 \times 11 = 77 \equiv -1 \ [26]$.
Question 7 : Quelles sont les solutions du système $x \equiv 2 \ [3]$ et $x \equiv 3 \ [5]$ ?
Réponse : B. Comme $3 \wedge 5 = 1$, le théorème chinois promet une seule solution modulo 15. Parmi 3, 8 et 13, les entiers de 0 à 14 qui valent 3 modulo 5, seul 8 vaut 2 modulo 3. Le piège 13 ne vérifie que la seconde équation, car $13 \equiv 1 \ [3]$.
Question 8 : Combien d'éléments inversibles compte $\mathbb{Z}/36\mathbb{Z}$ ?
Réponse : D. On écrit $36 = 4 \times 9$ avec $4 \wedge 9 = 1$, d'où $\varphi(36) = \varphi(4)\varphi(9) = 2 \times 6 = 12$. Le piège 4 calcule $\varphi(6) \times \varphi(6)$, alors que la formule du produit exige deux facteurs premiers entre eux.
Question 9 : Quel est l'ordre de $\bar 2$ dans le groupe des inversibles de $\mathbb{Z}/7\mathbb{Z}$ ?
Réponse : A. On a $2^2 = 4$, puis $2^3 = 8 \equiv 1 \ [7]$ : l'ordre vaut 3, qui divise bien $\varphi(7) = 6$. Le piège 6 prend l'exposant de Fermat pour l'ordre, alors que Fermat ne donne qu'un multiple de l'ordre.
Question 10 : Quel est le reste de $2^{100}$ dans la division par 13 ?
Réponse : C. Le nombre 13 est premier et ne divise pas 2, donc $2^{12} \equiv 1 \ [13]$. Avec $100 = 12 \times 8 + 4$, on obtient $2^{100} \equiv 2^4 = 16 \equiv 3 \ [13]$. Le piège 1 applique Fermat comme si 100 était un multiple de 12.
Question 11 : Lequel de ces éléments engendre le groupe $(\mathbb{Z}/12\mathbb{Z}, +)$ ?
Réponse : D. Une classe $\bar k$ engendre ce groupe si et seulement si $k \wedge 12 = 1$, et seul 5 convient. Le piège $\bar 3$ confond « nombre premier » et « premier avec 12 » : ses multiples ne donnent que $\bar 0$, $\bar 3$, $\bar 6$ et $\bar 9$.
Question 12 : Lequel de ces anneaux est isomorphe à $\mathbb{Z}/12\mathbb{Z}$ ?
Réponse : B. Le théorème chinois s'applique à $12 = 3 \times 4$, car $3 \wedge 4 = 1$. Le piège A a bien 12 éléments, mais chacun vérifie $6x = 0$, alors que dans $\mathbb{Z}/12\mathbb{Z}$ il faut 12 additions de $\bar 1$ pour revenir à $\bar 0$.
Question 13 : Quelles sont les solutions de $6x \equiv 4 \ [10]$ ?
Réponse : A. Ici $6 \wedge 10 = 2$ divise 4 : on divise tout par 2, modulo compris, d'où $3x \equiv 2 \ [5]$, puis $x \equiv 2 \times 2 = 4 \ [5]$ car 2 est l'inverse de 3 modulo 5. Modulo 10, cela donne $x \equiv 4$ ou $x \equiv 9$. Le piège C garde le modulo 10 et perd 9, qui marche pourtant : $6 \times 9 = 54 \equiv 4 \ [10]$.
Question 14 : Quelles sont les solutions de $x^2 = \bar 1$ dans $\mathbb{Z}/8\mathbb{Z}$ ?
Réponse : D. On teste les huit classes : $3^2 = 9$, $5^2 = 25$ et $7^2 = 49$ valent 1 modulo 8, comme $1^2$, et les classes paires ont pour carré $\bar 0$ ou $\bar 4$. Le piège B raisonne comme dans un corps, où $(x - \bar 1)(x + \bar 1) = \bar 0$ force $x = \pm \bar 1$ ; or ici, pour $x = \bar 3$, ce produit vaut $\bar 2 \times \bar 4 = \bar 0$.
Question 15 : On sait que $2^{10} = 1024 = 3 \times 341 + 1$. Laquelle de ces affirmations est juste ?
Réponse : B. On a $2^{340} = (2^{10})^{34} \equiv 1 \ [341]$, alors que $341 = 11 \times 31$. Le petit théorème de Fermat ne marche que dans un sens : il part d'un nombre premier, et cette congruence ne prouve donc pas que 341 est premier, d'où le piège A. Quant à l'ordre de $\bar 2$, il vaut 10, pas 340.
Sources
Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation, programme de mathématiques des classes MP et MPI (2021), partie « Structures algébriques usuelles ».