Maintenant que nous savons résoudre une simple équation, nous sommes en droit de nous demander comment résoudre un système de plusieurs équations. En utilisant le point théorique précédent, nous pouvons les résoudre une par une pour (si elles admettent toutes une solution) nous ramener à un système du type
$$\left\{ \begin{align}
x &\equiv a_1 \pmod {n_1} \\
x &\equiv a_2 \pmod {n_2} \\
&\vdots \\
x &\equiv a_k \pmod {n_k} \\
\end{align}\right.$$
Exemple
Un exemple populaire de tel système est le problème suivant.
Ce problème se réécrit facilement en un système d'équation. Si on note $x$ le nombre de billes, alors nous savons que
$$\left\{ \begin{align}
x &\equiv 1 \pmod {2} \\
x &\equiv 0 \pmod {3} \\
x &\equiv 2 \pmod {5} \\
\end{align}\right.$$ Il n'est a priori pas évident qu'il existe bel et bien une solution à ce problème, et encore moins de la trouver. Le théorème des restes chinois va, sous quelques conditions, nous assurer l'existence et l'unicité de la solution d'un tel système.
Énoncé
Le théorème des restes chinois s'énonce en toute généralité comme suit.
Théorème des restes chinois
Si $n_1, n_2, \dots, n_k$ sont des nombres premiers entre eux deux à deux, et si $a_1, a_2, \dots, a_k$ sont des nombres entiers, alors il existe un unique $x$ modulo $n_1\cdot \ldots \cdot n_k$ tel que
$$\left\{ \begin{align}
x &\equiv a_1 \pmod {n_1} \\
x &\equiv a_2 \pmod {n_2} \\
&\vdots \\
x &\equiv a_k \pmod {n_k} \\
\end{align}\right.$$
Le théorème fournit également une façon de construire $x$, mais nous allons la découvrir dans la preuve de l'existence de la solution.
Démonstration
- Montrons l'existence. Cherchons d'abord une solution au système plus simple (d'inconnue $x_1$)
$$\left\{ \begin{align}
x_1 &\equiv 1 \pmod {n_1} \\
x_1 &\equiv 0 \pmod {n_2} \\
&\vdots \\
x_1 &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ Un $x_1$ solution du système doit avant tout être multiple de $n_2, n_3, \dots, n_k$, et donc de leur produit $n_2\cdot n_3 \cdot \ldots \cdot n_k$ vu qu'ils sont premiers entre eux.
On peut donc noter $x_1 = n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot y_1$ et chercher $y_1$ tel que
$$n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot y_1 \equiv 1 \pmod {n_1}.$$ Il s'agit à nouveau d'une simple équation linéaire, et la solution est donnée par
$$y_1 \equiv (n_2\cdot n_3 \cdot \ldots \cdot n_k)^{-1} \pmod {n_1}.$$ On trouve par la même occasion $x_1$.
De la même façon, on peut pour chaque $i \in \left\{1, \dots, k\right\}$ trouver un $x_i$ qui soit solution du système avec des zéros partout et un $1$ dans la $i$-ème ligne.
Ce n'est alors plus qu'une formalité de vérifier que $x = a_1 \cdot x_1 + \dots + a_k \cdot x_k$ est solution du système initial.
- Montrons à présent l'unicité. Si $x$ et $x'$ vérifient tous les deux le système d'équations, alors on remarque que $x-x'$ vérifie
$$\left\{ \begin{align}
x - x' &\equiv 0 \pmod {n_1} \\
x - x' &\equiv 0 \pmod {n_2} \\
&\vdots \\
x - x' &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ ce qui signifie que $x-x' \equiv 0 \pmod {n_1 \cdot \ldots \cdot n_k}$, c'est-à-dire que $x$ et $x'$ sont égaux modulo $n_1 \cdot \ldots \cdot n_k$, d'où l'unicité annoncée.
Remarques
- Il se peut que l'on soit dans un cas où les nombres $n_1, \dots, n_k$ ne sont pas premiers entre eux deux à deux. Il est cependant toujours possible de se ramener à un système de ce type. Par exemple, si on considère le système
$$\left\{ \begin{align}
x &\equiv 13 \pmod {18} \\
x &\equiv 11 \pmod {12} \\
\end{align}\right.$$ il nous suffit de séparer le modulo $18$ en un modulo $2$ et un modulo $9$, ainsi que le modulo $12$ en un modulo $4$ et un modulo $3$, pour obtenir :
$$\left\{ \begin{align}
x &\equiv 13 \equiv 1 \pmod {2} \\
x &\equiv 13 \equiv 4 \pmod {9} \\
x &\equiv 11 \equiv 3 \pmod {4} \\
x &\equiv 11 \equiv 2 \pmod {3} \\
\end{align}\right.$$ On constate sur cet exemple que l'équation modulo $4$ est plus forte que l'équation modulo $2$, vu qu'un nombre congru à $3$ modulo $4$ est toujours congru à $3 \equiv 1$ modulo $2$. On peut donc laisser tomber l'équation modulo $2$. Par contre on remarque aussi que l'équation modulo $9$ contredit l'équation modulo $3$, vu qu'un nombre congru à $4$ modulo $9$ est toujours congru à $4 \equiv 1$ modulo $3$, et non à $2$. Vu que ces deux équations se contredisent, le système n'a pas de solution.
De manière générale, toute équation du type $x \equiv a \pmod {p_1^{e_1} p_2^{e_2} \ldots p_m^{e_m}}$ peut-être remplacée par les $m$ équations
$$\left\{ \begin{align}
x &\equiv a \pmod {p_1^{e_1}} \\
x &\equiv a \pmod {p_2^{e_2}} \\
& \ \ \vdots\\
x &\equiv a \pmod {p_m^{e_m}} \\
\end{align}\right.$$ Si l'on part d'un système où les nombres $n_1, \ldots, n_k$ ne sont pas premiers entre eux, on peut donc toujours utiliser la décomposition en facteurs premiers de chacun des $n_i$ pour se ramener à un système d'équations dont les modulos sont tous des puissances de nombres premiers. On obtient alors, pour certains $p$, plusieurs équations modulo une puissance de $p$. Il y a deux cas de figure pour chacun de ceux-ci :
- Soit ces équations se contredisent (comme c'était le cas avec les équations modulo $3$ et $9$ ci-dessus), auquel cas le système n'a pas de solution ;
- Soit l'équation avec le plus grand modulo est plus forte que toutes les autres (comme c'était le cas avec les équations modulo $2$ et $4$ ci-dessus), auquel cas on peut garder l'équation la plus forte uniquement.
À la fin de ce processus, soit on a trouvé une contradiction, soit il nous reste des équations dont les modulos sont des puissances de nombres premiers deux à deux distincts et on peut enfin appliquer le théorème des restes chinois.
- Dans les problèmes un peu avancés, c'est surtout l'existence d'une solution qui est primordiale et il est rare qu'il soit nécessaire de connaître sa construction. Il n'est cependant pas compliqué de retenir la démarche à suivre, à savoir résoudre d'abord les systèmes simplifiés.
- Le mieux pour bien comprendre cette démarche étant de la faire sur un exemple, nous vous conseillons d'essayer de résoudre l'exemple des billes ci-dessus. Vous devriez trouver $y_1 = 1$, $x_1 = 15$, $y_2 = 1$, $x_2 = 10$, $y_3 = 1$, $x_3=6$ et donc $x = 27$. À noter que cette solution est unique modulo $30$ : il se peut que je possède $57$ billes !