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 1 \pmod {3} \\
x &\equiv 2 \pmod {6} \\
\end{align}\right.$$ il nous suffit de modifier la deuxième équation pour obtenir :
$$\left\{ \begin{align}
x &\equiv 1 \pmod {3} \\
x &\equiv 2 \pmod {2} \\
x &\equiv 2 \pmod {3} \\
\end{align}\right.$$ On constate sur cet exemple que nous sommes en présence de deux équations se contredisant (la première et la troisième), ce qui signifie qu'il n'existe pas de solution.
- 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 !