SOMMAIRE
1. Présentation
1.1 Le problème
1.2 Conditions d'existence de solutions
2.1 Recherche d’une solution particulière
2.2 Recherche de toutes les solutions
2.3 Le cas de trois modules ou plus
3. Les congruences simultanées au baccalauréat
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.
Étant donnés les entiers $a$, $b$,$m$ et $n$, on cherche à résoudre dans $?$ le système de congruences simultanées :
Résoudre ce système est équivalent à résoudre le système
En égalant les deux équations, on en déduit l’équation :
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 :
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 :
En multipliant par $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.
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 :
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.
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) :
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 :
L’algorithme d’Euclide va nous permettre de trouver une solution particulière $(x_0, y_0)$ de $?^2$ de l’équation diophantienne $(E)$.
En multipliant par 3, nous obtenons :
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
est équivalente à
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.
En soustrayant membre à membre les deux équations nous obtenons :
.
À 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 :
Remplaçons alors $y + 6$ dans l’équation $(F)$ pour déterminer $x$ :
d’où
Finalement,
Réciproquement, vérifions que ces valeurs sont bien solutions de l’équation $(E)$ :
Donc, les solutions dans $\mathbb{?}^2$ de l’équation $(E)$ sont les couples$ :
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 :
Maintenant, pour que $(x, y)$ soit solution de (E), nous devons avoir :
ce qui donne
L’ensemble des solutions du système de congruences simultanées $(S)$ est :
On considère le système :
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 \ne i}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 :
On démontrerait que les solutions du système $(S)$ s’écrivent alors :
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).
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 :
Partie A : Question de cours
1. Énoncer le théorème de Bézout et le théorème de Gauss.
2. Démontrer le théorème de Gauss en utilisant le théorème de Bézout.
Partie B
Il s’agit de résoudre dans $?$ le système
1. Démontrer qu’il existe un couple $(u, v)$ d’entiers relatifs tel que :$19u + 12v = 1$
(On ne demande pas dans cette question de donner un exemple d’un tel couple).
Vérifier que, pour un tel couple, le nombre $N = 13 \times 12v + 6 \times 19u$ est une solution de $(S)$.
2.a. Soit $n_0$ une solution de $(S)$, vérifier que le système $(S)$ équivaut à $\displaystyle{\left\{\begin{array}{l l} n \equiv n_0 (19) \\ n \equiv n_0 (12) \end{array}\right.}$
b. Démontrer que le système $\displaystyle{\left\{\begin{array}{l l} n \equiv n_0 (19) \\ n \equiv n_0 (12) \end{array}\right.}$ équivaut à $n \equiv n_0 (12 \times 19)$.
Trouver un couple $(u, v)$ solution de l’équation $19u + 12v = 1$ et calculer la valeur de $N$ correspondante.
b. Déterminer l’ensemble des solutions de $(S)$ (on pourra utiliser la question 2.b.).
4. Un entier naturel $n$ est tel que lorsqu’on le divise par 12 le reste est 6 et lorsqu’on le divise par 19 le reste est 13. On divise $n$ par $228 = 12 \times 19$. Quel est le reste $r$ de cette division ?
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.