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.