Association pour l'Innovation Didactique
Centre de Recherche et d'Expérimentation pour l'Enseignement des Mathématiques

Théorème des restes chinois 

pré-requis: théorème de Bezout sur l'anneau Z


Résolution du problème des restes chinois grâce au théorème de Bezout

On se donne quatre entiers r, s, a et b; on cherche à résoudre le système de congruence suivant , d'inconnue le nombre entier x:

 (i) .

L'existence d'une solution n'est pas assurée: prendre a = b et r et s différents modulo a pour s'en convaincre.
Ce type de problème s'est d'abord présenté aux astronomes. Très tôt la science chinoise avait réussi à mettre au point une technique pour dater des événements grâce à deux (ou plus) événements astronomiques simultanés.


Nous allons dans ce qui suit associer le système (i) à un engrenage, ce qui aura l'avantage, entre autres vertus, de jeter les bases intuitives pour l'objet Z /aZ et d'introduire la notion de Plus Petit Commun Multiple (PPCM) comme la période d'un comportement cyclique.

Deux roues crantées A et B forment un engrenage. Ces roues ont respectivement a et  b dents (et donc autant d'encoches). Nous allons chercher à déterminer s'il est possible que  la rième dent de la roue A vienne en contact avec la sième encoche de la roue B. Si oui, nous voulons repérer combien de contacts ont été réalisés avant celui-ci. 
Dans certains cas qu'il vous faudra identifier, la figure ci-dessous calcule automatiquement le nombre de contacts nécessaires depuis la position initiale, c'est-à-dire depuis que la première dent de la roue A était en contact avec la première encoche de la roue B. L'imagiciel propose soit de faire tourner le système (touche P, puis flèches du clavier), soit d'aller directement à la solution par appui sur la touche X. Les quatre variables a, b, r, s sont également pilotables: pour sélectionner l'une d'entre elle, appuyez sur l'une des touches A, B, R, S, puis pilotez la variable grâce aux flèches du clavier.

Exemple 1: (i)     Appuyez sur la touche 1 , puis sur les flèches du clavier pour faire tourner l'engrenage. La troisième dent (sur 25) de la roue A et la septième encoche (sur 28) de la roue B coïncident après 203 contacts. On peut "y aller" directement par appui sur la touche X. Il faut attendre le 903ième contact pour obtenir de nouveau cette coïncidence. On aurait peut-être pu le deviner, car  903-203=700=PPCM(25,28).

Exemple 2: (ii) Appuyez sur la touche 2 , puis sur les flèches du clavier pour faire tourner l'engrenage. La troisième dent (sur 44) de la roue A et la septième encoche (sur 28) de la roue B coïncident après 91 contacts. On peut "y aller" directement par appui sur la touche X. Remarquez que 44 et 28 ne sont pas premiers entre eux. Il faut attendre le 399ième contact pour obtenir de nouveau cette coïncidence. On aurait peut-être pu le deviner, car  399-91=308=PPCM(44,28).
Exemple 3: (iii) Appuyez sur la touche 3 , puis sur les flèches du clavier pour faire tourner l'engrenage. La figure ne répond pas de manière satisfaisante à l'appui sur la touche X ; au bout de 308 (=PPCM(44,28)) contacts, il est raisonnable de renoncer à trouver une solution, puisque l'on retrouve exactement la position relative initiale des deux roues.

Exercice:
1-a Montrons qu'il suffit que PGCD(a,b)=1 pour que le système admette une solution. 
Soit a et b tels que  PGCD(a,b)=1.  Considérons alors (u,v) un couple de Bezout , i.e. tel que au + bv =1; montrer que 
X = r + au(s-r) est une solution possible, et que l'ensemble des solutions est S = X+PPCM(a,b) Z.
1-b  la condition PGCD(a,b) = 1 n'est pas nécessaire, comme le montre l'exemple 2; chercher un contre-exemple beaucoup plus trivial sans l'aide de la figure.
1-c  En fait, on a la caractérisation suivante, dont on vous demande d'achever  la démonstration:
  Théorème Le système  a une solution si et seulement si PGCD(a,b) | r-s
PGCD(a,b)=1 (tout comme r = s) est donc bien une condition suffisante pour que le système ait une solution. 

Démonstration à compléter: 
sens direct : si le système a une solution X, alors il existe un couple d'entiers (q1, q2) tel que    et par simple soustraction des deux équations, 0 =  r - s + a q1 - b q2 , soit r - s = b q2 - a q1 ; or on a vu plus haut que l'ensemble des combinaisons au'+bv' où u' et v' parcourent Z coïncide avec l'ensemble des multiples de δ=PGCD(a,b). En particulier pour u'= -q1 et v' = q2 :    b q2 - a q1 est un multiple de δ, autrement dit δ | r-s.
réciproque : supposons que δ | r-s, où δ = PGCD(a,b) = au+bv pour un couple de Bezout (u,v); 
soit k l'entier tel que s-r = kδ.
Vérifiez que l'entier X= r + auk est solution du système, et que l'ensemble des solutions est S = X+PPCM(a,b)Z .

 2- Pour un système  à trois (ou plus) équations, l'illustration du problème est meilleure avec une crémaillère qui engendre trois rotations synchrones (les trois roues tournent simultanément du même nombre de dents).
Il s'agit alors de déterminer s'il est possible que la crémaillère soit simultanément en contact avec la rième dent de la roue A, la sième dent la roue B et la tième  de la roue C. Si oui, la figure suivante repère combien de contacts ont été réalisés avant celui-ci; on peut directement aller à cette solution par appui sur la touche X
2-a Enoncez une condition suffisante pour que le système ait une solution. 
2-b Essayez de construire avec Géoplan une solution plus élégante que la recherche brute du premier indice nul de la suite w (cf. texte de la figure: w(n) désigne le nombre de conditions non remplies parmi les trois voulues, après n contacts).

Remarque
En termes algébriques modernes, le problème des restes chinois est souvent présenté comme résoluble, grâce au lemme d'un théorème "chinois" d'isomorphisme entre les groupes Z /abZ   et Z /aZ *Z /bZ   dès que a et b sont premiers entre eux. Ce lemme affirme que la fonction f candidate à être l'isomorphisme est surjective.