Introduction : Une Nouvelle Forme d’Égalité
Introduite par Carl Friedrich Gauss, la notion de congruence est une manière de relâcher la condition d’égalité stricte. Au lieu de demander si deux nombres sont égaux, on se demande s’ils se « ressemblent » d’une certaine manière. Dans les anneaux euclidiens comme $\mathbb{Z}$ et $K[X]$, cette ressemblance est définie par le fait d’avoir le même reste lors de la division par un élément fixe (un entier ou un polynôme).
Cette idée simple est extraordinairement puissante. Elle permet de simplifier des problèmes complexes en les réduisant à l’étude d’un nombre fini de cas (les restes possibles). L’arithmétique des congruences, ou arithmétique modulaire, est non seulement un domaine fascinant de l’algèbre, mais elle est aussi le langage fondamental sur lequel reposent la cryptographie moderne, la théorie des codes et la construction de nouvelles structures algébriques comme les anneaux quotients et les corps finis.
Les Congruences dans l’Anneau des Entiers $\mathbb{Z}$
C’est le cadre le plus connu, celui de « l’horloge arithmétique ». On s’intéresse aux restes dans la division par un entier $n$.
Soit $n$ un entier naturel non nul. Deux entiers $a$ et $b$ sont dits congrus modulo $n$, et on note $a \equiv b \pmod{n}$, s’ils ont le même reste dans la division euclidienne par $n$.
Une définition équivalente, et souvent plus pratique, est : $$ a \equiv b \pmod{n} \iff n \text{ divise } (a-b) $$
Exemple
Modulo 7 :
- $15 \equiv 1 \pmod{7}$ car $15 = 2 \cdot 7 + 1$.
- $22 \equiv 1 \pmod{7}$ car $22 = 3 \cdot 7 + 1$.
- Donc, $15 \equiv 22 \pmod{7}$. On peut aussi vérifier que $7$ divise $22-15=7$.
- De même, $-6 \equiv 1 \pmod{7}$ car $-6 = (-1) \cdot 7 + 1$.
La relation de congruence est une relation d’équivalence : elle est réflexive ($a \equiv a$), symétrique (si $a \equiv b$ alors $b \equiv a$) et transitive (si $a \equiv b$ et $b \equiv c$ alors $a \equiv c$).
Plus important encore, elle est compatible avec les opérations d’addition et de multiplication :
Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors :
- $a+c \equiv b+d \pmod{n}$
- $a \cdot c \equiv b \cdot d \pmod{n}$
Cette compatibilité nous permet de définir une structure d’anneau sur l’ensemble des classes d’équivalence, l’anneau quotient $\mathbb{Z}/n\mathbb{Z}$.
Les Congruences dans l’Anneau des Polynômes $K[X]$
Le concept se transpose de manière parfaitement analogue à l’anneau des polynômes, en remplaçant l’entier $n$ par un polynôme non nul $P(X)$.
Soit $P(X)$ un polynôme non nul de $K[X]$. Deux polynômes $A(X)$ et $B(X)$ sont dits congrus modulo $P(X)$, et on note $A(X) \equiv B(X) \pmod{P(X)}$, s’ils ont le même reste dans la division euclidienne par $P(X)$.
Définition équivalente : $$ A(X) \equiv B(X) \pmod{P(X)} \iff P(X) \text{ divise } (A(X)-B(X)) $$
Exemple dans $\mathbb{R}[X]$
Soit le module $P(X) = X^2+1$.
- $A(X) = X^3+X+2$. La division par $X^2+1$ donne $X^3+X+2 = X(X^2+1) + 2$. Le reste est 2. Donc $X^3+X+2 \equiv 2 \pmod{X^2+1}$.
- $B(X) = 2X^2+2$. La division par $X^2+1$ donne $2X^2+2 = 2(X^2+1) + 0$. Le reste est 0. Donc $2X^2+2 \equiv 0 \pmod{X^2+1}$.
- $C(X) = X^2+3$. La division par $X^2+1$ donne $X^2+3 = 1(X^2+1) + 2$. Le reste est 2. Donc $X^2+3 \equiv 2 \pmod{X^2+1}$.
- Par conséquent, $A(X) \equiv C(X) \pmod{X^2+1}$.
Comme dans $\mathbb{Z}$, la congruence modulo $P(X)$ est une relation d’équivalence, et elle est compatible avec l’addition et la multiplication des polynômes.
Ceci permet de construire l’anneau quotient $K[X]/(P(X))$. Les éléments de cet anneau sont les classes d’équivalence. Chaque classe peut être représentée de manière unique par son reste dans la division par $P(X)$, c’est-à-dire par un polynôme de degré strictement inférieur à $\deg(P)$.
Par exemple, dans $\mathbb{R}[X]/(X^2+1)$, tout polynôme est congru à un unique polynôme de la forme $aX+b$. Les calculs dans cet anneau se font en calculant « modulo $X^2+1$ ». Dans cet anneau, la classe de $X^2$ est congrue à $-1$, ce qui est la base de la construction des nombres complexes : $$ X^2 \equiv -1 \pmod{X^2+1} $$