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
,
,
et
, on
cherche à résoudre dans
le système
de
congruences simultanées :
1.2
Conditions d'existence de solutions
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
est solution de
, alors
.
Conformément à ce que nous annonce Euler (cf.
chapitre
4), cette équation diophantienne a
des solutions si et seulement si
est un multiple du
P.G.C.D. de
et
. En effet, notons
le P.G.C.D. de
et
. On peut alors écrire :
et
où
et
sont deux entiers non nuls premiers entre
eux. Le
théorème de Bézout
assure alors
l’existence de deux entiers
et
tels que :
En multipliant par
:
Ceci nous montre bien que si
est un multiple du
P.G.C.D. de
et
alors
l’équation
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 :
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) :
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
prend la forme :
, ici .
2.1 Recherche
d’une solution
particulière
L’algorithme d’Euclide va nous
permettre de trouver une solution particulière
de
de l’équation diophantienne
.
donc .
En multipliant par 3, nous obtenons :
.
Donc le couple (– 3, – 6) est une solution
particulière de l’équation
.
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
et
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
par ce P.G.C.D. on obtient une
équation de la même forme à
coefficients
entiers dont les coefficients de
et de
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.
2.2 Recherche
de toutes les solutions
2.2.1 Résolution de
l’équation
Soit
) un couple d’entiers solution de
,
alors :
En soustrayant membre à membre les deux équations
nous obtenons :
.
À partir de cette équation, nous trouvons
et
grâce au théorème de Gauss. En
effet, puisque
16 divise
et qu’il est premier avec 9, il divise
. Il existe alors un entier
tel que :
.
Remplaçons alors
dans
l’équation
pour déterminer
:
,
d’où
.
Finalement,
et ,
où .
Réciproquement, vérifions que ces valeurs sont
bien solutions de l’équation
:
.
Donc, les solutions dans
de
l’équation
sont les couples
.
Une méthode légèrement
différente permet de résoudre
l’équation
). En appliquant deux
fois le théorème de Gauss, nous
trouvons :
tel que ,
tel que .
Maintenant, pour que
soit solution de (E), nous devons
avoir :
,
soit , soit .
Nous trouvons alors les mêmes solutions que
précédemment.
2.2.2 Les solutions du système
Une fois que nous avons les solutions de
l’équation
, il suffit de remplacer
par
par exemple, dans l’expression de
:
,
ce qui donne
.
L’ensemble des solutions du système de congruences
simultanées
est :
{}.
2.3 Le cas de
trois modules ou plus
On considère le système :
où
est un entier supérieur ou égal
à deux, les
sont des entiers, et les modules
sont
premiers entre eux deux à deux.
Notons
et pour
Dès que
,
et
sont premiers entre eux
donc, pour tout entier
de 1 à
,
est premier
avec
donc, en appliquant le théorème de
Bézout, il existe un entier
tel que :
.
On démontrerait que les solutions du système
s’écrivent alors :
, où 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 :
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
d’entiers relatifs tel que :
(On ne demande pas dans cette question de donner un exemple
d’un tel couple).
Vérifier que, pour un tel couple, le nombre
est une solution de
.
2.a. Soit
une solution de
, vérifier que le
système
équivaut à
b. Démontrer que le système
équivaut à
.
Trouver un couple
solution de l’équation
et calculer la valeur de
correspondante.
b. Déterminer l’ensemble des solutions de
(on pourra utiliser la question 2.b.).
4. Un entier naturel
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
par
.
Quel est le reste
de cette
division ?
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 :
et
étant
deux entiers
naturels non nuls premiers entre eux, les anneaux
et
sont isomorphes.