Le Théorème des Restes Chinois

Introduction : Un Pont entre les Mondes Modulaires

Le théorème des restes chinois est un résultat fondamental de la théorie des nombres et de l’algèbre commutative. Il tire son nom de textes mathématiques chinois anciens, où des problèmes de ce type ont été étudiés pour la première fois. Dans sa forme la plus simple, il répond à une question très naturelle : peut-on trouver un nombre qui laisse des restes spécifiques lorsqu’il est divisé par plusieurs diviseurs différents ?

Par exemple, si je cherche un nombre qui, divisé par 3, laisse un reste de 2, et qui, divisé par 5, laisse un reste de 3, existe-t-il une solution ? Est-elle unique ? Le théorème des restes chinois non seulement garantit l’existence et l’unicité (modulo le produit des diviseurs) d’une telle solution, mais il fournit également une méthode pour la construire.

Au-delà de ces énigmes arithmétiques, le théorème possède une formulation plus abstraite et puissante en termes d’isomorphisme d’anneaux. Il établit un lien profond entre l’arithmétique dans $\mathbb{Z}/n\mathbb{Z}$ et l’arithmétique dans des anneaux plus petits, ce qui en fait un outil indispensable en cryptographie (notamment pour l’algorithme RSA), en informatique pour la manipulation de grands nombres, et en théorie des codes.

Énoncé du Théorème

Soient $n_1, n_2, \dots, n_k$ des entiers supérieurs à 2, deux à deux premiers entre eux (c’est-à-dire $\text{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 unique solution modulo $N = n_1 n_2 \dots n_k$.

Méthode de Résolution : Une Approche Constructive

La preuve du théorème est constructive, ce qui signifie qu’elle nous donne un algorithme pour trouver la solution $x$. Illustrons la méthode générale.

On pose $N = n_1 n_2 \dots n_k$. Pour chaque $i \in \{1, \dots, k\}$, on définit $N_i = \frac{N}{n_i}$. Puisque les $n_j$ sont premiers entre eux deux à deux, il est clair que $\text{pgcd}(N_i, n_i) = 1$.

Grâce au théorème de Bézout, puisque $N_i$ et $n_i$ sont premiers entre eux, on sait qu’il existe un inverse pour $N_i$ modulo $n_i$. Notons cet inverse $u_i$ : $$ N_i u_i \equiv 1 \pmod{n_i} $$ (On peut trouver $u_i$ grâce à l’algorithme d’Euclide étendu).

Maintenant, construisons des « briques de base ». Pour chaque $i$, définissons $e_i = N_i u_i$. Ces nombres ont une propriété remarquable :

  • Par construction, $e_i \equiv 1 \pmod{n_i}$.
  • Pour tout $j \neq i$, $n_j$ divise $N_i$, donc $e_i = N_i u_i \equiv 0 \pmod{n_j}$.

La solution du système est alors simplement une combinaison linéaire de ces briques de base : $$ x_0 = a_1 e_1 + a_2 e_2 + \dots + a_k e_k = \sum_{i=1}^k a_i N_i u_i $$ Vérifions que $x_0$ est bien une solution. Pour un $j$ quelconque, regardons $x_0$ modulo $n_j$ : $$ x_0 \pmod{n_j} = \left(\sum_{i=1}^k a_i e_i\right) \pmod{n_j} $$ Dans cette somme, tous les termes $e_i$ sont nuls modulo $n_j$ sauf pour $i=j$, où $e_j \equiv 1 \pmod{n_j}$. Il ne reste donc que : $$ x_0 \equiv a_j e_j \equiv a_j \cdot 1 \equiv a_j \pmod{n_j} $$ Ceci est vrai pour tous les $j$, donc $x_0$ est bien une solution. L’ensemble de toutes les solutions est alors $\{ x_0 + mN \mid m \in \mathbb{Z} \}$.

Exemple Détaillé

Résolvons le système suivant : $$ \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases} $$

  1. Identifier les paramètres :
    • $a_1=2, n_1=3$
    • $a_2=3, n_2=5$
    • $a_3=2, n_3=7$
    Les moduli 3, 5, 7 sont bien premiers entre eux. Le module final est $N = 3 \times 5 \times 7 = 105$.
  2. Calculer les $N_i$ :
    • $N_1 = N/n_1 = 105/3 = 35$
    • $N_2 = N/n_2 = 105/5 = 21$
    • $N_3 = N/n_3 = 105/7 = 15$
  3. Trouver les inverses $u_i$ :
    • On cherche $u_1$ tel que $35u_1 \equiv 1 \pmod 3$. Comme $35 \equiv 2 \pmod 3$, on cherche $2u_1 \equiv 1 \pmod 3$. On trouve $u_1 = 2$ (car $2 \times 2 = 4 \equiv 1 \pmod 3$).
    • On cherche $u_2$ tel que $21u_2 \equiv 1 \pmod 5$. Comme $21 \equiv 1 \pmod 5$, on trouve directement $u_2 = 1$.
    • On cherche $u_3$ tel que $15u_3 \equiv 1 \pmod 7$. Comme $15 \equiv 1 \pmod 7$, on trouve directement $u_3 = 1$.
  4. Construire la solution : $$ x_0 = a_1 N_1 u_1 + a_2 N_2 u_2 + a_3 N_3 u_3 $$ $$ x_0 = (2)(35)(2) + (3)(21)(1) + (2)(15)(1) $$ $$ x_0 = 140 + 63 + 30 = 233 $$
  5. Finaliser la solution : La solution est unique modulo 105. On calcule donc le reste de 233 par 105 : $$ 233 = 2 \times 105 + 23 $$ La solution est $x \equiv 23 \pmod{105}$.
    Vérification : $23 \div 3 = 7 \text{ reste } 2$, $23 \div 5 = 4 \text{ reste } 3$, $23 \div 7 = 3 \text{ reste } 2$. C’est correct.

La Version Abstraite : Un Isomorphisme d’Anneaux

Le théorème a une formulation plus élégante et puissante dans le langage de l’algèbre moderne. Il établit que la structure de l’anneau $\mathbb{Z}/N\mathbb{Z}$ est « la même » que celle du produit des anneaux plus petits.

Théorème Chinois (Version Anneaux)

Soient $n_1, \dots, n_k$ des entiers deux à deux premiers entre eux. Soit $N = n_1 \dots n_k$. Alors l’application $$ \begin{array}{rcl} f: \mathbb{Z}/N\mathbb{Z} & \to & \mathbb{Z}/n_1\mathbb{Z} \times \dots \times \mathbb{Z}/n_k\mathbb{Z} \\ \bar{x} & \mapsto & (x \pmod{n_1}, \dots, x \pmod{n_k}) \end{array} $$ est un isomorphisme d’anneaux.

Cela signifie que $f$ est une bijection qui préserve les opérations d’addition et de multiplication. Le fait que $f$ soit une bijection est exactement l’affirmation de la version « congruence » du théorème : pour chaque $k$-uplet de restes $(a_1, \dots, a_k)$, il existe un unique $\bar{x}$ qui s’envoie dessus.

Cet isomorphisme est extrêmement utile. Il permet de transformer un calcul compliqué modulo $N$ en une série de calculs plus simples modulo les $n_i$. Par exemple, pour calculer $A^E \pmod N$ (une opération centrale en RSA), on peut calculer $a_i = A^E \pmod {n_i}$ pour chaque $i$, puis utiliser le théorème des restes chinois pour reconstruire la solution finale. C’est souvent beaucoup plus rapide.