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- Le texte d'Ibn al-Haytham

Au Nom de Dieu Clément et Miséricordieux. Dieu a la Toute-Puissance.
Traité d'al-Hassan b. al-Hassan b. al-Haytham, sur la résolution d'un problème numérique [1]

Problème

Trouver un nombre tel que si on le divise par deux il en reste un; si on le divise par trois, il en reste un; si on le divise par quatre, il en reste un; si on le divise par cinq, il en reste un; si on le divise par six, il en reste un; si on le divise par sept, il n'en reste rien.

Solution

Le problème est indéterminé, c'est-à-dire qu'il admet beaucoup de solutions. Pour les trouver, il y a deux méthodes. L'une des deux méthodes est la méthode canonique : on multiplie les nombres mentionnés, qui divisent le nombre cherché, les uns par les autres; on ajoute 1 au produit; c'est le nombre cherché. Je veux dire qu'on multiplie deux par trois, le produit par quatre, ensuite le produit par cinq, et enfin le produit par six; on ajoute ensuite un au produit; c'est le nombre cherché.

Le produit de ces nombres les uns par les autres selon l'ordre que nous avons mentionné est 720; on ajoute un à 720, on a 721 qui sera le nombre, et ceci parce que 720 se divise par deux, car il a une moitié, par trois car il a un tiers, par quatre car il a un quart, par cinq car il a un cinquième, par six car il a un sixième. Si donc 720 se divise par chacun de ces nombres, alors si on divise 721 par chacun de ces nombres, il en reste toujours un, et 721 se divise par sept, car il a un septième. Le nombre cherché répondant à la propriété précédemment mentionnée est 721.

On peut trouver le nombre cherché par une autre méthode, qui est la méthode par laquelle on montre que ce problème a plusieurs solutions, et même une infinité de solutions. Il s'agit de trouver le plus petit nombre qui a une moitié, un tiers, un quart, un cinquième et un sixième, c'est-à-dire le plus petit nombre multiple des nombres qui précèdent le sept, et qui est soixante. On divise soixante par sept, il reste quatre. On cherche alors un nombre qui a un septième et tel que si on en retranche un, le reste ait un quart. Il peut se trouver beaucoup de nombres répondant à cette propriété; la méthode pour trouver ce nombre est de prendre sept, d'en retrancher un, il reste six; on ajoute sept, sept, à six, jusqu'à ce qu'on aboutisse à un nombre qui ait un quart. Si l'addition aboutit alors à un nombre ayant un quart, on ajoute un à ce nombre. La somme aura un septième.

Exemple. On ajoute sept à six, on a 13 qui n'a pas de quart; on ajoute alors sept à 13, on a 20 qui a un quart ; on ajoute alors un à 20, on a 21 qui a un septième. On prend le quart de 20 qui est 5, on le multiplie par 60, on a donc trois cents, auquel on ajoute un; on a donc 301, qui est le nombre cherché; et ceci parce que 300 a une moitié, un tiers, un quart, un cinquième, un sixième, donc trois cents se divise par 2, par 3, par 4, par 5 et par 6. Et si 300 se divise par ces nombres, sans qu'il n'en reste rien, alors, si on divise trois cent un par chacun de ces nombres, il en reste 1, et 301 a un septième ; il se divise donc par 7, et il n'en reste rien. Trois cent un est donc le nombre cherché.

De même, si on prend six auquel on ajoute sept, sept, jusqu'à ce qu'on obtienne la somme 20, à laquelle on ajoute ensuite sept, sept, quatre fois, la somme aura alors un quart, et si on lui ajoute un, la somme aura un septième. Si on ajoute sept, sept, quatre fois à 20, cela donne 48, qui a un quart, si on ajoute un à 48, on a 49, qui a un septième. On prend alors le quart de 48, qui est 12, qu'on multiplie par 60; on a alors 720, auquel on ajoute un ; on a enfin 721, qui est le nombre cherché, et qui est le nombre obtenu suivant la première manière.

De même, si on ajoute sept, sept, quatre fois à 48, cela donnera 76, qui a un quart; si on ajoute un à 76, cela donnera 77, qui a un septième. On prend le quart de 76, qui est 19, qu'on multiplie par 60, on aura alors 1140, auquel on ajoute un; on a donc 1141, qui est le nombre cherché, et ceci parce que 1140 a une moitié, un tiers, un quart, un cinquième et un sixième, et 1141 a un septième. De même, si on ajoute sept, sept, quatre fois à 76, on a 104; si on prend son quart qui est 26, si on le multiplie par 60 et si on ajoute un au produit, on a le nombre cherché. Et ainsi de suite, indéfiniment, chaque fois qu'on ajoute au nombre auquel on aboutit sept, sept, quatre fois, qu'on prend le quart de la somme, qu'on le multiplie par 60 et qu'on ajoute un, on a le nombre cherché.

De cette manière, on peut trouver une infinité de nombres dont chacun divisé par 2, 3, 4, 5, 6 donne comme reste un, et dont chacun se divise par sept. S'il en est ainsi, au lieu d'ajouter sept, sept, quatre fois à 20, et de prendre le quart de la somme, on ajoute à 5, qui est le quart de 20, une seule fois sept, et on obtient 12. Et de même pour 48, au lieu de lui ajouter sept, sept, quatre fois, et de prendre le quart de cette somme, on ajoute à 12 une seule fois sept. La méthode pour trouver les nombres cherchés est de prendre le quart de 20, qui est 5, auquel on ajoute sept, sept, toujours, indéfiniment [2]. Si on multiplie ensuite chacun de ces nombres par 60, et si on ajoute un au produit, chacun des nombres obtenus selon cet ordre est le nombre cherché. Ceci est la solution de ce problème.

Ceci étant montré, nous disons que cette propriété [3] est nécessaire pour tout nombre premier, c'est-à-dire que pour tout nombre premier – qui est le nombre qui n'est multiple que de l'unité –, si on multiplie les nombres qui le précèdent les uns par les autres selon la manière que nous avons introduite, et si on ajoute un au produit, alors si on divise la somme par chacun des nombres qui précèdent le nombre premier, il en reste un, et si on la divise par le nombre premier, il n'en reste rien.

Et selon la deuxième manière également, si on trouve le plus petit nombre multiple des nombres qui précèdent le nombre premier, c'est-à-dire le plus petit nombre dont les parties homonymes sont les nombres qui précèdent le nombre premier ; si ensuite on divise ce nombre par le nombre premier, on retient le reste, et on retient la partie homonyme de ce reste pour l'utiliser comme mesure. Par exemple, si on divise 60 par 7, il reste 4, dont la partie homonyme est un quart, qui est la mesure. La partie homonyme d'un nombre est le nombre qui divise le nombre dont il est la partie autant de fois qu'il y a d'unités dans le nombre dont on dit qu'il est son homonyme. On retient donc la partie homonyme du reste, on prend le nombre premier duquel on retranche un comme on a fait pour sept, on ajoute à la différence [4] le nombre premier autant de fois que nécessaire, jusqu'à aboutir à un nombre qui a pour partie homonyme le reste, c'est-à-dire la partie qu'on a retenue.

Du nombre auquel on a abouti, on prend la partie homonyme du reste, et on la multiplie par le nombre qui est le plus petit nombre dont les parties homonymes sont les nombres qui précèdent le nombre premier, on ajoute un au résultat, ce qu'on obtient est le nombre cherché. Si on ajoute au nombre, qui est la partie homonyme du reste, le nombre premier autant de fois que l'on veut, si on multiplie chacun de ces nombres par le nombre qui est le plus petit nombre qui a les parties mentionnées, successivement, et si on ajoute à chacun d'eux le nombre un, chacun des nombres obtenus selon cette propriété est le nombre cherché. Ainsi, si on multiplie chacun des nombres 12 et 19 par 60, et si on ajoute un à chacun des produits, on a le nombre cherché. Si donc on divise un des nombres obtenus suivant cette propriété par le plus petit nombre qui a pour parties homonymes les nombres qui précèdent le nombre premier, le reste est seulement un. Que l'on retranche un du premier nombre, et qu'on multiplie la différence (après l'avoir divisée par le plus petit nombre qui a pour parties homonymes les nombres qui précèdent le nombre premier, et après avoir ajouté au résultat le nombre sept autant de fois que l'on veut) par le plus petit nombre qui a pour parties homonymes les nombres qui précèdent le nombre premier, on ajoute un au résultat et on a le nombre cherché.

Si on suit cette méthode pour tout nombre premier, alors pour tout nombre trouvé de cette manière, si on le divise par chacun des nombres qui précèdent le nombre premier, il en reste un, et si on le divise par le nombre premier, il n'en reste rien.

Ce que nous venons de mentionner englobe les réponses à tous les problèmes de ce genre, et que Dieu nous assiste.

La réponse au problème numérique est achevée. Louange à Dieu Seigneur du Monde; Béni soit Son Prophète Mohamed, l'Élu, et tous les Siens.

2- Commentaires

Pour un lecteur d’aujourd’hui, la compréhension du texte d’Ibn al-Haytham est parfois difficile. Après avoir traité un cas particulier, il énonce une procédure générale, correspondant au problème suivant :

Soit $p$ un nombre premier supérieur ou égal à cinq (le cas où $p$ est égal à 3 est élémentaire). Nous devons chercher toutes les solutions du système de congruences :

$\displaystyle{\left\{\begin{array}{l l} x \equiv 1 (modn), n = 2, 3 ..., p-1   (1)\\ x \equiv 0 (modp)  (2) \end{array}\right.}$

Sans le justifier, l’auteur ramène la résolution des $(p – 2)$ congruences de (1) à celle d’une seule congruence :

$\displaystyle{ x \equiv 1 (modM)~~(3)}$

où $M$ désigne le plus petit commun multiple des nombres entiers strictement inférieurs au nombre premier $p$. L’équivalence des congruences (1) et (3) se prouve comme il suit.
Notons $M = {a_1}^{\alpha_1}.{a_2}^{\alpha_2}...{a_q}^{\alpha_q}$ la décomposition de $M$ en facteurs premiers. Supposons l’équation (1) vérifiée; $x – 1$ étant divisible par tous les entiers de 2 à $p – 1$, il est divisible par chacun des ${a_i}^{\alpha_i}$ Comme ceux-ci sont premiers entre eux deux à deux, on en déduit à l’aide du théorème de Gauss que $x – 1$ est divisible par leur produit $M$. D’où la congruence (3).

Réciproquement, supposons (3) vérifiée; alors, $x – 1$ est divisible par $M$; et puisque $M$ est un multiple de chacun des entiers de 2 à $p – 1$, $x – 1$ est divisible par chacun de ces nombres. D’où la congruence (1).

Le système de départ est donc équivalent à : 

$\displaystyle{\left\{\begin{array}{l l} x \equiv 1 (modM) (3)\\ x \equiv 0 (modp)  (2) \end{array}\right.}$

Il suffit pour résoudre ce système d’utiliser un lien convenable entre les entiers $M$ et $p$. De manière naturelle, al-Haytham considère la division euclidienne de $M$ par $p$ :

$\displaystyle{ M = pQ+ R, 0 < R < p.~~(4)}$
Notons que, d’une part, $M$ est strictement supérieur à $p$ car ce nombre est supérieur ou égal à 5 et que d’autre part, le reste $R$ est non nul car le nombre premier $p$ est premier avec tous les entiers naturels qui lui sont strictement inférieurs et par suite avec le P. P. C. M de ces derniers, autrement dit il ne divise pas $M$. Ainsi le nombre $R$ ou son inverse, la « partie homonyme du reste » vont devenir la « mesure commune ».

D’après (3) on a $x = KM + 1$, avec $K$ entier, ce qui s’écrit d’après (4) :

$\displaystyle{ x = K( pQ + R) + 1 = p(KQ) + KR + 1}$
de telle sorte que le problème revient à la recherche des entiers naturels $K$ tels que

$\displaystyle{ KR +1}\equiv 0 (modp)}$,
soit à la recherche des entiers $K$ ou $Y$ tels que

$\displaystyle{ KR + 1 = Yp}$.
La « mesure commune » étant associée au reste $R$, l’auteur détermine son multiple $K$, en opérant à partir d’ajouts successifs de l’entier $p$. Il prend en compte le premier entier naturel $y$ tel que

$\displaystyle{ p -1+ py = KR,~~soit~~p -1+ py\equiv 0 (modR)}$.

Al-Haytham ne démontre pas qu’il est toujours possible d’obtenir un tel nombre $y$. Or, il en est bien ainsi. Il suffit de considérer tous les entiers naturels $y$ strictement inférieurs à $R$ et de montrer que, modulo $R$, tous les nombres $(p -1+ py)$ sont distincts. En effet, nous aurons alors, modulo $R$, $R$ nombres distincts de la forme $(p -1+ py$) dont, par suite, un seul est nul. Il nous reste donc à démontrer que, modulo $R$, tous les nombres $(p -1+ py)$ sont distincts. Raisonnons par l’absurde et supposons qu’il existe deux tels nombres $y'$ et $y''$ distincts et strictement inférieurs à $R$ tels que

$\displaystyle{ p -1 + py' \equiv p-1 + py'' (mod R)}$.

Nous avons alors, par soustraction

$\displaystyle{ p |y'- y''| \equiv 0 (mod R)}$.
Or, le reste $R$ étant strictement inférieur au nombre premier $p$, il est premier avec ce nombre et par suite il doit diviser $|y'- y''|$, ce qui est impossible puisque les nombres $y'$ et $y''$ sont distincts et strictement inférieurs à $R$. Autrement dit, modulo $R$, tous les nombres $(p -1+ py$) sont distincts et on aboutit bien au nombre cherché, c’est à dire au nombre $X$ tel que

$\displaystyle{ X = p -1 + py \equiv 0 (mod R)}$.
Par exemple, pour p égal à 7, nous avons

$\displaystyle{ M = 60~~et~~ R = 4~~et~~ p \equiv 3 (mod 4)}$.

On obtient alors, modulo 4 :

$\displaystyle{ p -1 \equiv 2, p -1+ p \equiv 1, p -1 + p + p \equiv 0}$.
Afin d’obtenir la solution x donnée par l’égalité (4), il suffit alors de prendre pour nombre $K$, en utilisant la « mesure commune », « la partie homonyme du reste », c’est-à-dire le résultat de la division de $X$ par $R$ ou de la « multiplication de $X$ par $1/R$ ». Tout nombre entier de la forme

$\displaystyle{ x = KM +1 +\lambda pM}$,

où le nombre entier naturel $\lambda$ est quelconque, est alors solution du problème.

Retour Sommaire 
Retour Chapitre 3