Le théorème des restes chinois
Textes, commentaires et activités pour l’arithmétique au lycée

1- Présentation

Nous étudions, dans ce chapitre, la résolution d’un système de deux congruences simultanées, les modules étant premiers entre eux, telle qu’elle serait menée au lycée. Même si nous nous appuyons sur un problème historique, nous employons les notations modernes, notamment le signe de congruence introduit par Gauss.

1.1 Le problème

Étant donnés les entiers $a$, $b$,$m$ et $n$, on cherche à résoudre dans $ℤ$ le système de congruences simultanées :

$\displaystyle{(S)~~\left\{\begin{array}{l l} z \equiv a (mod m) \\ z \equiv b(mod n) \end{array}\right}.$

1.2 Conditions d'existence de solutions

Résoudre ce système est équivalent à résoudre le système 

$\displaystyle{\exists(x,y)\in \mathbb{Z}^2:\left\{\begin{array}{l l} z =a+mx \\ z = b +ny \end{array}\right}$.

En égalant les deux équations, on en déduit l’équation :

$\displaystyle{(E)~~mx – ny = b – a}.

Réciproquement, si $(x, y)$ est solution de $(E)$, alors $a + mx = b + ny = z$.

Conformément à ce que nous annonce Euler (cf. chapitre 4), cette équation diophantienne a des solutions si et seulement si $b – a$ est un multiple du P.G.C.D. de $m$ et $n$. En effet, notons $d$ le P.G.C.D. de $m$ et $n$. On peut alors écrire :

$m = dm'$ et $n = dn'$

où $m'$ et $n'$ sont deux entiers non nuls premiers entre eux. Le théorème de Bézout assure alors l’existence de deux entiers $u$ et $v$ tels que :

$\displaystyle{m'u – n'v = 1}.

En multipliant par $d$ :

$\displaystyle{mu – nv = d}.

Ceci nous montre bien que si $b – a$ est un multiple du P.G.C.D. de $m$ et $n$ alors l’équation $(E)$ a des solutions. La réciproque est immédiate.

1.3 Contre-exemple eulérien

Dans le paragraphe 15 du texte dans lequel il traite cette question (Chapitre 3), Euler donne un exemple de système n’admettant pas de solution :

$\displaystyle{\left\{\begin{array}{l l} z \equiv 13(mod24) \\ z \equiv 9(mod15) \end{array}\right.}$

Avant d’énoncer le résultat précédent, il nous donne l’argument suivant : selon la deuxième congruence, la solution devrait être un multiple de 3 mais la première implique le contraire.

2. Résolution du problème

Nous allons maintenant montrer sur un exemple comment on procède actuellement pour résoudre ce système de congruences simultanées lorsqu’il possède des solutions. Soit le système (voir le chapitre 4, Euler, § 16) :

$\displaystyle{(S)~~\left\{\begin{array}{l l} z \equiv 1(mod16) \\ z \equiv 7(mod9) \end{array}\right.}$

16 et 9 sont premiers entre eux donc d’après le critère précédent, le système a des solutions. L’équation $(E)$ prend la forme :

$\alphax + \betay = \gamma$, ici $16x – 9y = 6 ~~(E)$.

2.1 Recherche d’une solution particulière

L’algorithme d’Euclide va nous permettre de trouver une solution particulière $(x_0, y_0)$ de $ℤ^2$ de l’équation diophantienne $(E)$.

$16 = 1 \times 9 + 7$

$9 = 1 \times 7 + 2$ donc $2 = 16 \times (– 1) – 9 \times (– 2)$.

En multipliant par 3, nous obtenons :

$16 \times(– 3) – 9 \times (– 6) = 6$.

Donc le couple (– 3, – 6) est une solution particulière de l’équation $(E)$.

Remarques :
a- On pourrait poursuivre l’algorithme d’Euclide jusqu’au P.G.C.D. des deux modules mais il suffit de s’arrêter dès que le reste divise la différence des restes du système initial. C’est ce que fait Euler.
b- Dans le cas où les modules $m$ et $n$ ne sont pas premiers entre eux et où il existe une solution, leur P.G.C.D. divise la différence des restes. En divisant ainsi chaque membre de l’équation $(E)$ par ce P.G.C.D. on obtient une équation de la même forme à coefficients entiers dont les coefficients de $x$ et de $y$ sont premiers entre eux.

Par exemple, l’équation

$42x + 72y = 30$

est équivalente à

$7x + 12y = 5$

en simplifiant par P.G.C.D.(42 ; 72) = 6. Les nombres 7 et 12 sont alors premiers entre eux. Cette remarque va nous permettre de supposer les modules premiers entre eux pour la suite.

2.2 Recherche de toutes les solutions

2.2.1 Résolution de l’équation $(E)$

Soit $(x, y$) un couple d’entiers solution de $(E)$, alors :

$\displaystyle{\left\{\begin{array}{l l} 16x – 9y = 6 \\ 16\times(– 3) – 9\times(– 6) = 6 \end{array}\right.}$

En soustrayant membre à membre les deux équations nous obtenons :

$(F)~~ 16(x + 3) = 9(y + 6)$ .

À partir de cette équation, nous trouvons $x$ et $y$ grâce au théorème de Gauss. En effet, puisque 16 divise $9(y + 6)$ et qu’il est premier avec 9, il divise $y + 6$. Il existe alors un entier $k$ tel que :

$y + 6 = 16k$.

Remplaçons alors $y + 6$ dans l’équation $(F)$ pour déterminer $x$ :

$16(x + 3) = 9 \times 16k$, d’où

$x + 3 = 9k$.

Finalement,

$x = 9k – 3$ et $y = 16k – 6$, où $k \in ℤ$.

Réciproquement, vérifions que ces valeurs sont bien solutions de l’équation $(E)$ :

$16x – 9y = 16(9k – 3) – 9(16k – 6) = 6$.

Donc, les solutions dans $\mathbb{ℤ}^2$ de l’équation $(E)$ sont les couples$ :

$(x, y) = (9k – 3, 16k – 6), k \in \mathbb{ℤ}$.

Une méthode légèrement différente permet de résoudre l’équation $(F$). En appliquant deux fois le théorème de Gauss, nous trouvons :

$ \exists k_1 \in ℤ$ tel que $x = 9k_1 - 3$, $\exists k_2 \in ℤ$ tel que $y = 16k_2 - 6$.

Maintenant, pour que $(x, y)$ soit solution de (E), nous devons avoir :

$16(x + 3) = 9(y + 6)$,

soit $16\times9k_1 = 9 \times16k_2$, soit $k_1 = k_2$.

Nous trouvons alors les mêmes solutions que précédemment.


2.2.2 Les solutions du système $(S)$

Une fois que nous avons les solutions de l’équation $(E)$, il suffit de remplacer $x$ par $9k – 3$ par exemple, dans l’expression de $z$ :

$ z = 16x + 1$

$z = 16(9k – 3) + 1~~ (k \in \mathbb{ℤ})$,

ce qui donne

$z = 144k – 47~~ (k \in \mathbb{ℤ})$.

L’ensemble des solutions du système de congruences simultanées $(S)$ est :

{$z \in \mathbb{ℤ} : \exists k \in \mathbb{ℤ}, z = 16 \times 9k – 47}$}.

2.3 Le cas de trois modules ou plus

On considère le système :

$ (S)~~z \equiv r_i (mod~ m_i)~~pour~~i = 1, …, p$

où $p$ est un entier supérieur ou égal à deux, les $r_i$ sont des entiers, et les modules $m_i$ sont premiers entre eux deux à deux.

Notons $M = \prod_{i=1}^{p}m_i$ et pour $i=1,...,p,~~M_i=\prod_{j\nei}m_j=\frac{M}{m_i}.

Dès que $j \ne i}$, $m_j$ et $m_i$ sont premiers entre eux donc, pour tout entier $i$ de 1 à $p$, $m_i$ est premier avec $M_i$ donc, en appliquant le théorème de Bézout, il existe un entier $u_i$ tel que :

$u_iM_i \equiv 1 (mod~m_i)$.

On démontrerait que les solutions du système $(S)$ s’écrivent alors :

$z=\sum_{i=1}^{p}u_iM_ir_i + kM$, où $k$ est un entier.

Nous retrouvons la forme précédente. Nous retrouvons aussi la forme des solutions donnée par Maître Sun (voir Chapitre 1), par Euler (voir le Chapitre 4) et par Gauss (Chapitre 5).

3. Les congruences simultanées au baccalauréat

De tels problèmes de congruences simultanées ont déjà été posés au baccalauréat des séries scientifiques, spécialité mathématiques : Asie, juin 1999 ; France métropolitaine, juin 2006 ; Antilles-Guyane, septembre 2008 ; Asie, juin 2009.

Voici, par exemple, l’exercice posé en 2006 s’appuyant sur une démarche différente :

Pour conclure ce chapitre

En guise de conclusion, précisons que dans l’enseignement supérieur, le théorème des restes chinois est énoncé en termes d’isomorphisme d’anneaux : $m$ et $n$ étant deux entiers naturels non nuls premiers entre eux, les anneaux $ℤ/mℤ \times ℤ/nℤ$ et $ℤ/(mn)ℤ$ sont isomorphes.