En arithmétique modulaire, on s’intéresse souvent à trouver un entier $x$ qui satisfait simultanément plusieurs équations de congruence. Un tel ensemble d’équations est appelé un système de congruences.
Le théorème des restes chinois fournit une condition d’existence et d’unicité pour la solution d’un tel système, ainsi qu’une méthode pour la construire.
Soient $n_1, n_2, \dots, n_k$ des entiers supérieurs à 1 qui sont premiers entre eux deux à deux (c’est-à-dire $pgcd(n_i, n_j) = 1$ pour tout $i \neq j$).
Alors, pour toute suite d’entiers $a_1, a_2, \dots, a_k$, le système de congruences : $$ \begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases} $$ admet une solution unique modulo le produit $N = n_1 n_2 \dots n_k$.
Démonstration (Constructive)
La démonstration fournit un algorithme pour trouver la solution.
Étape 1 : Existence
Posons $N = n_1 n_2 \dots n_k$. Pour chaque $i \in \{1, \dots, k\}$, définissons $N_i = \frac{N}{n_i}$.
Puisque les $n_j$ sont premiers entre eux deux à deux, $N_i$ et $n_i$ sont premiers entre eux. D’après le théorème de Bachet-Bézout, il existe donc un entier $y_i$, appelé l’inverse de $N_i$ modulo $n_i$, tel que : $$ N_i y_i \equiv 1 \pmod{n_i} $$
Considérons maintenant le nombre $x_0$ construit comme suit : $$ x_0 = a_1 N_1 y_1 + a_2 N_2 y_2 + \dots + a_k N_k y_k = \sum_{i=1}^k a_i N_i y_i $$ Montrons que $x_0$ est une solution du système. Pour un $j$ fixé, regardons $x_0$ modulo $n_j$ : $$ x_0 \equiv \sum_{i=1}^k a_i N_i y_i \pmod{n_j} $$ Si $i \neq j$, alors $N_i$ est un multiple de $n_j$, donc $a_i N_i y_i \equiv 0 \pmod{n_j}$. La somme se simplifie et il ne reste que le terme pour $i=j$ : $$ x_0 \equiv a_j N_j y_j \pmod{n_j} $$ Par construction de $y_j$, on a $N_j y_j \equiv 1 \pmod{n_j}$. On obtient donc : $$ x_0 \equiv a_j \cdot 1 \pmod{n_j} $$ Ceci étant vrai pour tout $j$, $x_0$ est bien une solution du système.
Étape 2 : Unicité
Supposons qu’il existe deux solutions, $x$ et $x’$. On a alors $x \equiv a_i \pmod{n_i}$ et $x’ \equiv a_i \pmod{n_i}$ pour tout $i$.
Par conséquent, leur différence $x – x’$ est congrue à 0 modulo $n_i$ pour chaque $i$. Cela signifie que $x – x’$ est un multiple de chaque $n_i$.
Puisque les $n_i$ sont premiers entre eux deux à deux, si un nombre est un multiple de chacun d’eux, il doit être un multiple de leur produit. Donc, $x – x’$ est un multiple de $N = n_1 n_2 \dots n_k$.
Cela signifie que $x \equiv x’ \pmod{N}$. La solution est donc unique modulo $N$.
Implications et Utilisation
- Isomorphisme d’anneaux : Le théorème est équivalent à l’existence d’un isomorphisme entre l’anneau $\mathbb{Z}/N\mathbb{Z}$ et le produit des anneaux $\mathbb{Z}/n_1\mathbb{Z} \times \dots \times \mathbb{Z}/n_k\mathbb{Z}$.
- Calcul et Algorithmique : Il est utilisé pour effectuer des calculs sur de très grands nombres en les décomposant en calculs plus simples sur des moduli plus petits.
- Cryptographie : Il intervient dans certaines étapes de l’algorithme RSA pour accélérer les calculs.