Nous venons de voir un exemple de système d'équations linéaires. Ce n'était qu'un exemple, mais la démarche que nous avons suivie pour le résoudre est en fait tout à fait générale ! Nous sommes donc en mesure de démontrer le théorème suivant :
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 \in \mathbb Z$, 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.$$
Nous avons déjà démontré ce théorème sur le cas particulier des billes de Jean, où $k = 3$, $n_1 = 2$, $n_2 = 3$, $n_3 = 7$, $a_1 = 1$, $a_2 = 2$ et $a_3 = 4$. Nous avons en effet vu qu'il existait une unique solution modulo $2\cdot 3\cdot 7 = 42$. Et nous avons même vu comment construire cette solution.
Le théorème des restes chinois se démontre en suivant exactement les mêmes étapes que celles que nous avons suivies pour le problème des billes.
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 d'une simple équation linéaire, dont on trouve la solution en multipliant par l'inverse $a$ de $n_2\cdot n_3 \cdot \ldots \cdot n_k$ modulo $n_1$ :
$$y_1 \equiv a \pmod {n_1}.$$ Une solution $x_1$ au système simplifié est donc donnée par $x_1 = n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot a$, où $a$ est l'inverse de $n_2\cdot n_3 \cdot \ldots \cdot n_k$ modulo $n_1$.
De la même façon, on peut pour chaque $i \in \left\{1, \dots, k\right\}$ trouver un $x_i$ solution du système
$$\left\{ \begin{align}
x_i &\equiv 0 \pmod {n_1} \\
x_i &\equiv 0 \pmod {n_2} \\
&\vdots \\
x_i &\equiv 1 \pmod {n_i} \\
&\vdots \\
x_i &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ (avec un $1$ uniquement sur la $i$-ème ligne).
Il ne reste alors plus qu'à considérer le nombre $x = a_1 \cdot x_1 + \ldots + a_k \cdot x_k$, dont on vérifie qu'il vaut $a_i$ modulo $n_i$ pour tout $i \in \{1, \ldots, k\}$. C'est bien une solution de notre 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
- En présence d'un système où des coefficients apparaissent devant $x$ sur certaines lignes (comme $5x \equiv 1 \pmod 7$), il semble à première vue que le théorème n'est pas applicable. Rappelons-nous cependant qu'une équation du type $ax \equiv b \pmod n$ est une simple équation linéaire qui peut être transformée en $x \equiv ba^{-1} \pmod n$, pourvu que $a$ possède un inverse $a^{-1}$ modulo $n$. On peut donc faire disparaître les éventuels coefficients devant $x$, pour se ramener à une situation où le théorème des restes chinois peut être utilisé. Par exemple, $5x \equiv 1 \pmod 7$ se transforme simplement en $x \equiv 3 \pmod 7$.
- Il se peut aussi 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 toutefois 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 (grâce au théorème des restes chinois) 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.