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

Voici une séquence de travail scénarisée autour d’un texte proposant un algorithme qui permet de résoudre un système de trois congruences simultanées modulo des entiers premiers entre eux deux à deux.

1- Un problème chinois: le problème de maître Sun

Acte 1: préparation à la maison

On trouve dans un livre de mathématiques chinois, que l’on peut dater entre les III^e et VI^e siècles, le problème suivant [1] :


a) Mettre ce problème en équations, éventuellement à l’aide des congruences.
b) Proposer une solution à ce problème.
c) Y a-t-il plusieurs solutions ? Si oui, combien ?

Acte 2 : synthèse du travail préparé et travail en classe

L’auteur propose la procédure suivante :


Remarque pour l’enseignant : dans la plupart des exemples trouvés, les auteurs préfèrent donner la plus petite solution strictement positive.

a) Vérifier que la réponse ainsi obtenue répond bien au problème.
b) Cette procédure est précisée par une méthode plus générale :

« En général : pour chaque unité restante d’un décompte par 3, poser 70 ; pour chaque unité restante d’un décompte par 5, poser 21, pour chaque unité restante d’un décompte par 7, poser 15. Si [la somme ainsi obtenue] vaut 106 ou plus, ôter 105 pour obtenir la réponse. »

En notant $a$, $b$ et $c$ les restes dans les divisions respectives par 3, 5 et 7, vérifier que le nombre $x$ est bien solution, avec :

$x = 70 a + 21 b + 15 c – 105 k~(où~ k \in ℕ.)$

Mais d’où viennent ces valeurs (70, 21, 15 et 105) ? L’auteur donne une réponse mais nous allons étudier un autre algorithme permettant de les calculer sous certaines conditions.

2- L'algorithme de Ratisbonne

L’algorithme que nous allons étudier maintenant est tiré d’un ouvrage, La pratique de l’algorithme de Ratisbonne, écrit par Frater Fridericus, un moine bénédictin qui vécut en Allemagne, à Ratisbonne, au XV^e siècle (voir chapitre 3 à paraître). Le problème que nous étudierons ici est issu d’une partie de l’ouvrage consacrée aux énigmes. La méthode proposée permet de déterminer les coefficients de Bézout, dans le cas où ils existent, sans utiliser l’algorithme d’Euclide.

2.1 Deux exemples pour comprendre

- Un premier exemple (à faire ensemble) 

Le problème chinois ci-dessus peut être interprété, à l’aide des congruences, comme la recherche des entiers $x$ vérifiant le système :

$\displaystyle{\left\{\begin{array}{l l} x \equiv 2(mod3) \\ x \equiv 3(mod5)\\x \equiv 2(mod7) \end{array}\right.}$

La solution repose sur l’obtention de trois entiers $\alpha$, $\beta$ et $\gamma$ tels que :

$\displaystyle{\left\{\begin{array}{l l} (5\times7)\alpha \equiv 1(mod3) \\ (3\times7)\beta \equiv 1(mod5)\\(3\times5)\gamma \equiv 1(mod7) \end{array}\right.}$

1. Justifier par un théorème du cours l’existence de ces trois entiers.

2. Pour trouver $\alpha$, on divise par 3 les multiples successifs de 35 (= 5 × 7). $\alpha$ sera le premier coefficient n pour lequel le reste de la division de 35n par 3 vaudra 1. Ici,

- Pour n = 1 : 35 = 11 × 3 + 2 ;
- Pour n = 2 : 2 × 35 = 70 = 23 × 3 + 1.

Donc $\alpha$ = 2 et 70 (= 2× 5×7)$\equiv$ 1 (mod 3)

Considérer de la même façon les multiples successifs de 21 (= 3 × 7) pour trouver le plus petit entier naturel $\beta$ tel que :

$\displaystyle{21\beta \equiv 1(mod 5).}$
Trouver de même le plus petit entier naturel $\gamma$ pour lequel :

$\displaystyle{15\gamma \equiv 1(mod 7).}$

3. On pose alors :

$\displaystyle{x = 35\alpha a + 21\beta b + 15\gamma c + 105k,~où~k \in \mathbb{ℤ}}$

Expliquer comment on obtient le nombre 105.
Vérifier que les nombres ainsi obtenus sont solutions du texte chinois.

Remarque pour l’enseignant : on obtient en fait toutes les solutions du problème mais ce n’est pas l’objectif de ce travail. On pourra avec profit se référer au chapitre 2.


- Un deuxième exemple à la main (à faire tout seul)

On considère maintenant le système :

$\displaystyle{(S)~\left\{\begin{array}{l l} x \equiv a(mod3) \\ x \equiv b(mod4)\\x \equiv c(mod5) \end{array}\right.} }$ où $a$, $b$,$c$ sont des entiers.

En utilisant la méthode précédente, démontrer que les entiers

$\displaystyle{x = 20\alpha a + 15\beta b + 12\gamma c + 60k,~où~k \in \mathbb{ℤ}}$

sont solutions du système $(S)$.

2.2 La théorie pour démontrer

Soient $A$, $B$ et $C$ trois entiers naturels supérieurs ou égaux à 2 et premiers entre eux deux à deux. Soient $\alpha$, $\beta$ et $\gamma$ trois entiers naturels. Nous allons étudier un algorithme donnant des solutions (dans ℕ ou dans $\mathbb{ℤ}$) du système de congruences simultanées :

$\displaystyle{(S)~\left\{\begin{array}{l l} x \equiv a(modA) \\ x \equiv b(modB)\\x \equiv c(modC) \end{array}\right.}$ où $a$, $b$,$c$ sont des entiers.

$A$ étant premier avec $B$ et $C$, il est premier avec le produit $BC$. Nous en déduisons, par le théorème de Bézout, l’existence d’un entier a défini comme ci-dessous. On démontre de même l’existence des entiers $\beta$ et $\gamma$.
Soient trois entiers $\alpha$, $\beta$ et $\gamma$ tels que :

$\displaystyle{(S)~\left\{\begin{array}{l l} \alpha BC \equiv 1(modA) \\ \beta AC \equiv 1(modB)\\\gamma AB \equiv 1(modC) \end{array}\right.}$

Soit $k$ un entier relatif. Démontrer que

$\displaystyle{x = \alpha a BC + \beta b AC + \gamma cAB + kABC}$

est solution du système $(S)$.

a) La clé de l’algorithme consiste à déterminer les valeurs de $\alpha$, $\beta$ et $\gamma$. Voici en quoi il consiste pour $\alpha$ (le principe est le même pour $\beta$ et $\gamma$, puisqu’ils ont des rôles symétriques) :

On considère les multiples successifs de $BC$. $\alpha$ sera le premier coefficient tel que le reste de la division de $\alphaBC$ par $A$ est 1.

Remarque pour l’enseignant : la réalisation de la partie qui suit peut être détaillée de différentes façons selon les objectifs techniques visés.

b) Programmation de l’algorithme au tableur

i. Programmer cet algorithme au tableur pour le deuxième exemple ci-dessus.
ii. Généraliser cet algorithme pour qu’il puisse s’appliquer à n’importe quelles données des entiers $A$, $B$, $C$, $a$, $b$, $c$ répondant aux conditions du problème.

iii. Le texte dont est tiré cet algorithme contient un tableau qui donne les valeurs de $\alpha$, $\beta$ et $\gamma$ pour toute une liste de triplets $(A, B, C)$ (voir le chapitre 3, § 2.1). Parmi ceux-ci, on trouve :

· Pour $A$ = 5, $B$ = 6, $C$ = 7 : $\alphaBC$ = 128, $\betaAC$ = 175, $\gammaAB$ = 120.
· Pour $A$ = 9, $B$ = 11, $C$ = 13 : $\alphaBC$ = 1 144, $\betaAC$ = 936, $\gammaAB$ = 1 782.

Dans ces deux cas, une erreur s’est glissée. Appliquer l’algorithme pour la trouver.

c) Programmer cet algorithme à la calculatrice.

d) Faire ensuite tourner l’algorithme avec un logiciel d’algorithmes.

Retour Sommaire 
Retour Chapitre 1 Retour Chapitre 3