CultureMATH - accueil - contact

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

Sommaire du dossier


2- Problèmes de congruences résolus au lycée


D. Daumas, M. Guillemot, O. Keller, R. Mizrahi, M. Spiesser


Article déposé le 30/10/11 Toute reproduction pour publication ou à des fins commerciales, de la totalité ou d'une partie de l'article, devra impérativement faire l'objet d'un accord préalable avec l'éditeur (ENS Ulm). Toute reproduction à des fins privées, ou strictement pédagogiques dans le cadre limité d'une formation, de la totalité ou d'une partie de l'article, est autorisée sous réserve de la mention explicite des références éditoriales de l'article. 





SOMMAIRE





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 :
(S){za(modm)zb(modn).


1.2 Conditions d'existence de solutions

Résoudre ce système est équivalent à résoudre le système 
(x,y)2:{z=a+mxz=b+ny.
En égalant les deux équations, on en déduit l’équation :

(E)mxny=ba.


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 ba 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ʹ


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 :

mʹunʹv=1.


En multipliant par d :

munv=d.


Ceci nous montre bien que si ba 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 :
{z13(mod24)z9(mod15)
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) :
(S){z1(mod16)z7(mod9)
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 :

αx+βy=γ, ici 16x9y=6(E).

2.1 Recherche d’une solution particulière

L’algorithme d’Euclide va nous permettre de trouver une solution particulière (x0,y0) de 2 de l’équation diophantienne (E).

16=1×9+7

9=1×7+2 donc 2=16×(1)9×(2).


En multipliant par 3, nous obtenons :

16×(3)9×(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 :
{16x9y=616×(3)9×(6)=6
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×16k,
d’où

x+3=9k.


Finalement,

x=9k3 et y=16k6, où k.


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

16x9y=16(9k3)9(16k6)=6.


Donc, les solutions dans 2 de l’équation (E) sont les couples:

(x,y)=(9k3,16k6),k.


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 :

k1 tel que x=9k1-3, k2 tel que y=16k2-6.


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

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

soit 16×9k1=9×16k2, soit k1=k2.


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 9k3 par exemple, dans l’expression de z :

z=16x+1

z=16(9k3)+1(k),


ce qui donne

z=144k47(k).


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

{z:k,z=16×9k47}.


2.3 Le cas de trois modules ou plus

On considère le système :

(S)zri(modmi)pouri=1,,p


p est un entier supérieur ou égal à deux, les ri sont des entiers, et les modules mi sont premiers entre eux deux à deux.

Notons M=i=1pmi et pour i=1,...,p,Mi=jimj=Mmi.

Dès que ji, mj et mi sont premiers entre eux donc, pour tout entier i de 1 à p, mi est premier avec Mi donc, en appliquant le théorème de Bézout, il existe un entier ui tel que :

uiMi1(modmi).


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

z=i=1puiMiri+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 :

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

(S){n13(19)n6(12)


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×12v+6×19u est une solution de (S).

2.a. Soit n0 une solution de (S), vérifier que le système (S) équivaut à {nn0(19)nn0(12)

b. Démontrer que le système {nn0(19)nn0(12) équivaut à nn0(12×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×19. Quel est le reste r 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 : m et n étant deux entiers naturels non nuls premiers entre eux, les anneaux /m×/n et /(mn) sont isomorphes.