Congruence modulo $n$

Définition intuitive

La congruence modulo $n$ consiste à ne retenir des entiers que leur reste dans la division par $n$, en oubliant délibérément le quotient. C’est l’arithmétique de l’horloge (numérique) : trois heures après vingt-trois heures, il est deux heures, parce qu’on travaille modulo $24$.

Définition formelle

Soit $n\in\mathbb{N}^{*}$. Deux entiers $a,b\in\mathbb{Z}$ sont dits congrus modulo $n$, ce qu’on note
$$a\equiv b \pmod n,$$si $n$ divise $a-b$, c’est-à-dire s’il existe $k\in\mathbb{Z}$ tel que $a=b+kn$.

Proposition. C’est une relation d’équivalence sur $\mathbb{Z}$, compatible avec l’addition et la multiplication :
$$a\equiv a' \text{ et } b\equiv b'\ \Longrightarrow\ a+b\equiv a'+b'\quad\text{et}\quad ab\equiv a'b' \pmod n .$$

Preuve de la compatibilité multiplicative. Si $a'=a+kn$ et $b'=b+\ell n$, alors $a'b'=ab+n(a\ell+bk+k\ell n)$. $\square$

L’ensemble quotient, noté $\mathbb{Z}/n\mathbb{Z}$, hérite donc d’une structure d'anneau commutatif ; il possède exactement $n$ éléments, les classes $\overline{0},\overline{1},\dots,\overline{n-1}$, car la division euclidienne assure que tout entier est congru à un unique reste dans $\llbracket 0,n-1\rrbracket$.

Inversibilité. La classe $\overline{a}$ est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si $\mathrm{pgcd}(a,n)=1$. En effet, l’identité de Bézout $au+nv=1$ fournit $\overline{a}\,\overline{u}=\overline{1}$ ; réciproquement, $au\equiv 1$ signifie $au-1=kn$, donc tout diviseur commun de $a$ et $n$ divise $1$. Le groupe des inversibles $(\mathbb{Z}/n\mathbb{Z})^{\times}$ est ainsi d’ordre $\varphi(n)$, et
$$\mathbb{Z}/n\mathbb{Z} \text{ est un corps}\iff n \text{ est premier}.$$

Remarques

• Simplification interdite. On ne peut pas diviser librement : $2\cdot 3\equiv 2\cdot 0 \pmod 6$ sans que $3\equiv 0$. La règle exacte est $ac\equiv bc\pmod n\iff a\equiv b\pmod{n/\mathrm{pgcd}(c,n)}$ ; la simplification par $c$ n’est valide que si $\mathrm{pgcd}(c,n)=1$.
• Fermat et Euler. Le théorème de Lagrange appliqué à $(\mathbb{Z}/n\mathbb{Z})^{\times}$ donne $a^{\varphi(n)}\equiv 1\pmod n$ dès que $\mathrm{pgcd}(a,n)=1$ ; pour $n=p$ premier, on retrouve $a^{p-1}\equiv 1$ et, sans condition, $a^{p}\equiv a\pmod p$.
• Théorème des restes chinois. Si $\mathrm{pgcd}(m,n)=1$, l’application naturelle $\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ est un isomorphisme d’anneaux. Un système de congruences à modules premiers entre eux a donc toujours une solution, unique modulo le produit. On en déduit la multiplicativité de $\varphi$.
• Équations linéaires. L’équation $ax\equiv b\pmod n$ admet une solution si et seulement si $d=\mathrm{pgcd}(a,n)$ divise $b$, auquel cas elle en a exactement $d$ modulo $n$. C’est la traduction modulaire du théorème de Bézout.
• Structure du groupe des inversibles. $(\mathbb{Z}/n\mathbb{Z})^{\times}$ est cyclique si et seulement si $n\in\{1,2,4,p^{k},2p^{k}\}$ avec $p$ premier impair. Un générateur s’appelle alors une racine primitive modulo $n$. En particulier $(\mathbb{Z}/8\mathbb{Z})^{\times}\simeq(\mathbb{Z}/2\mathbb{Z})^{2}$ n’est pas cyclique.

Exemples

1. Horloge (à aiguilles). Modulo $12$, on a $23\equiv 11$ et $15+9\equiv 0$. Modulo $7$, les jours de la semaine : si aujourd’hui est un lundi, dans $100$ jours ce sera un mercredi, car $100\equiv 2\pmod 7$.
2. Carrés. Modulo $4$, un carré vaut $0$ ou $1$ ; modulo $8$, il vaut $0$, $1$ ou $4$. Il en résulte que $n\equiv 3\pmod 4$ n’est jamais somme de deux carrés, et que $x^{2}+y^{2}=3z^{2}$ n’a pas de solution entière non triviale.
3. Grandes puissances. Pour calculer $7^{100}\bmod 13$ : le petit théorème de Fermat donne $7^{12}\equiv 1$, et $100=8\cdot 12+4$, donc $7^{100}\equiv 7^{4}=2401\equiv 9\pmod{13}$.
4. Restes chinois. Le système $x\equiv 2\pmod 3$, $x\equiv 3\pmod 5$, $x\equiv 2\pmod 7$ a pour unique solution $x\equiv 23\pmod{105}$ — c’est l’énoncé du Sunzi Suanjing, du IIIᵉ siècle.
5. Cryptographie. Le système RSA repose sur $m^{ed}\equiv m\pmod{N}$ avec $N=pq$ et $ed\equiv 1\pmod{\varphi(N)}$ : chiffrer et déchiffrer sont deux exponentiations modulaires, et la sécurité tient à la difficulté de factoriser $N$.