Théorème des restes chinois

Le théorème des restes chinois est un résultat d'arithmétique modulaire traitant de résolution de systèmes de congruences. Ce résultat, établi initialement pour ℤ/nℤ, se généralise en théorie des anneaux. Ce théorème est utilisé en théorie des nombres.

Fragments d'histoire

La forme originale du théorème apparait sous forme de problème dans le livre de Sun Zi, le Sunzi suanjing datant du III^e siècle. Il est repris dans un livre du mathématicien chinois Qin Jiushao publié en 1247. Le résultat concerne les systèmes de congruences (voir arithmétique modulaire).

Soient des objets en nombre inconnu. Si on les range par 3 il en reste 2. Si on les range par 5, il en reste 3 et si on les range par 7, il en reste 2. Combien a-t-on d'objets?

Cette énigme est parfois associée au général Han Xin (en) comptant son armée

La résolution proposée par Sun Zi pour ce problème est la suivante:

Multiplie le reste de la division par 3, c’est-à-dire 2, par 70, ajoute lui le produit du reste de la division par 5, c’est-à-dire 3, avec 21 puis ajoute le produit du reste de la division par 7, c'est-à-dire 2 par 15. Tant que le nombre est plus grand que 105, retire 105.

Mais la solution n'explique qu'imparfaitement la méthode utilisée. On peut cependant remarquer que,

• 70 a pour reste 1 dans la division par 3 et pour reste 0 dans les divisions par 5 et 7
• 21 a pour reste 1 dans la division par 5 et pour reste 0 dans les divisions par 3 et 7
• 15 a pour reste 1 dans la division par 7 et pour 0 dans les divisions par 3 et 5

Le nombre 2 × 70 + 3 × 21 + 2 × 15 a bien alors pour restes respectifs 2, 3 et 2 dans les divisions par 3, 5 et 7. Enfin comme 105 a pour reste 0 dans les trois types de division, on peut l’ôter ou l'ajouter autant de fois que l'on veut sans changer les valeurs des restes. La plus petite valeur pour le nombre d'objets est alors de 23.

On retrouve ce problème presque à l'identique dans le Liber Abbaci de Fibonacci dans le chapitre XII qui concerne les problèmes et énigmes où l'on trouve également le problème des lapins de la suite de Fibonacci.

Selon Ulrich Libbrecht la motivation de ce type de calcul serait l'astronomie. On peut en effet penser que les Chinois, férus de calculs astronomiques, puissent être intéressés par des concordances de calendrier et qu'ils aient été amenés très tôt à s'intéresser à des questions du type :

Dans combien de jours la pleine lune tombera-t-elle au solstice d'hiver ?

Si la question se pose alors qu'il reste 6 jours avant le solstice d'hiver et 3 jours avant la pleine lune, la question se traduit par :

Existe-t-il un entier x tel que le reste de la division de x par 365 donne 6 et le reste de la division de x par 28 donne 3 ?

Mais selon Daumas et al. il s'agirait plus probablement de devinettes associées à des comptages par paquets

Enfin, il serait dommage de ne pas présenter ce problème concernant des pirates et un trésor, très fréquemment cité pour illustrer le théorème des restes chinois :

Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Un nouveau partage donnerait au cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner le reste des pirates ?

L'arithmétique modulaire a rendu ce type de problème plus facile à résoudre.

Système de congruences d'entiers

Théorème

Soient $n_1$, ..., $n_k$ des entiers deux à deux premiers entre eux (ce qui veut dire pgcd (n_i , n_j) = 1 lorsque i ≠ j). Alors pour tous entiers $a_1$, ..., $a_k$, il existe un entier $x$, unique modulo $n = \prod_{i=1}^k n_i$ et tel que

$\begin{matrix} x \equiv a_1\pmod{n_1}\\ \ldots \\ x \equiv a_k\pmod{n_k}\\ \end{matrix}$

Une solution x peut être trouvée comme suit:

Pour chaque i, les entiers $n_i$ et $\hat{n}_i = \frac n{n_i} = n_1\ldots n_{i-1}n_{i+1}\ldots n_k$ sont premiers entre eux, et d'après le théorème de Bachet-Bézout on peut trouver (en utilisant par exemple l'algorithme d'Euclide étendu) des entiers $u_i\,$ et $v_i\,$ tels que $u_in_i + v_i\hat n_i= 1$. Si on pose $e_i = v_i\hat n_i$, alors nous avons

$e_i \equiv 1 \pmod{n_i} \,$

et

$e_i \equiv 0 \pmod{n_j}\,$ pour j ≠ i.

Une solution particulière de ce système de congruences est par conséquent

$x = \sum_{i=1}^k a_i e_i~,$

et les autres solutions sont les entiers congrus à ce $x$ modulo le produit $n$.

Exemple

Le problème des soldats se réduit à

$x \equiv 2 \pmod{3}\,$

$x \equiv 3 \pmod{5}\,$

$x \equiv 2 \pmod{7} \,$

on obtient alors

• $n = 3 \times 5 \times 7$
• ${n_1} = 3$ et $\hat n_1 = 35$ , or $2\hat n_1\equiv 1 \pmod{3}$ donc $e_1 = 70$
• $n_2 = 5$ et $\hat n_2 = 21$ , or $\hat n_2\equiv 1 \pmod{5}$ donc $e_2 = 21$
• $n_3 = 7$ et $\hat n_3= 15$ , or $\hat n_3\equiv 1 \pmod{7}$ donc $e_3 = 15$

une solution pour x est alors $x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233$

et les solutions sont tous les entiers congrus à 233 modulo 105, c'est-à-dire à 23 modulo 105.

Généralisation à des nombres non premiers entre eux

Quelquefois, les systèmes de congruences peuvent être résolus même si les $n_i\,$ ne sont pas premiers entre eux deux à deux. Le critère précis est le suivant : une solution x existe si et seulement si $a_i \equiv a_j \pmod {Pgcd(n_i,n_j)}\,$ pour tous i et j. Toutes les solutions x sont congrues modulo le PPCM des n_i .

Exemple : résoudre le système

$x \equiv 3 \pmod{4} \,$

$x \equiv 5\pmod{6} \,$

équivaut à résoudre le système

$x \equiv 3 \pmod{4} \,$

$x \equiv 1 \pmod{2} \,$

$x \equiv 1 \pmod{2} \,$

$x \equiv 2\pmod{3} \,$

équivaut au système

$x \equiv 3 \pmod{4} \,$

$x \equiv 2\pmod{3}\,$

• $n_1 = 4$ et $\hat n_1 = 3$ , or $-\hat n_1\equiv 1 \pmod{4}$ donc $e_1 = -3$
• $n_2 = 3$ et $\hat n_2 = 4$ , or $\hat n_2\equiv 1 \pmod{3}$ donc $e_2 = 4$

Une solution est donc $x = 3 \times(-3)+ 2 \times 4 = -1$ ou tout autre nombre congru à 11 modulo 12.

La méthode des substitutions successives peut souvent fournir les solutions des systèmes de congruences, même lorsque les modules ne sont pas premiers entre eux deux à deux.

Une méthode générale pour résoudre le problème avec deux variables consiste à utiliser l'algorithme d'Euclide étendu pour résoudre l'équation diophantienne linéaire $x_1 \times n_1 - x_2 \times n_2 = a_2 - a_1$. Le reste peut alors être dérivé de $x_1$. Cette méthode peut s'appliquer itérativement pour résoudre le problème avec plus de deux variables.

Interprétation mécanique

La résolution du système suivant :

$\left\{\begin{array}{l} x\equiv r \pmod a \\ x\equiv s \pmod b \end{array}\right.$

d'inconnue $x$ passe par le calcul du PPCM de $a$ et $b$.

Ce problème mathématique est une modélisation d'un problème sur des engrenages: une roue dentée comportant $a$ dents s'engrène dans une tringle horizontale. Combien de dents doivent passer pour que sa $r$-ième dent vienne en coïncidence avec la $s$-ième dent d'une autre roue dentée comportant elle $b$ dents ?

Le PPCM des deux nombres $a$ et $b$ est ce qui permet de comprendre le comportement périodique de ce système : c'est le nombre de dents séparant deux contacts de même congruence. On peut donc trouver la solution, s'il y en a une, dans l'intervalle $[1,\rm{PPCM}(a,b)]$. Il y a une solution si PGCD(a , b) divise r - s.

On peut comprendre simplement pourquoi le calcul sur des roues dentées fait intervenir de l'arithmétique modulaire, en remarquant que l'ensemble des dents d'une roue en comptant n peut être paramétré par l'ensemble des racines nèmes de l'unité, qui a une structure de groupe naturellement isomorphe à celle de Z/nZ.

Résultat pour les anneaux

Dans les anneaux Z/nZ

Le théorème chinois a également une version plus abstraite : si $n_1$, ..., $n_k$ sont deux à deux premiers entre eux alors, en notant $n$ le produit des $n_i$, l'application (à valeurs dans l'anneau produit)

$\begin{matrix} \phi:&\mathbb{Z}/n\mathbb{Z} &\longrightarrow& \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}\\ &\alpha[n] &\longmapsto& (\alpha[n_1],\dots,\alpha[n_k]) \end{matrix}$

est un isomorphisme d'anneaux.

Pour le montrer, on remarque d'abord que les deux ensembles $\mathbb{Z}/n\mathbb{Z}$ et $\mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}$ ont le même nombre d'éléments. Comme $\phi\,$ est un morphisme d'anneaux, il suffit donc de démontrer qu'il est injectif pour en déduire que c'est un isomorphisme. Pour cela, il suffit de montrer que son noyau est réduit à 0 : si $\alpha=0[n_i]$ pour $i=1, \dots, k$, c’est-à-dire si $\alpha$ est un multiple de chaque $n_i$, alors $\alpha=0[n]$, c’est-à-dire $\alpha$ est un multiple du produit $n_1\dots n_k$. Ceci résulte de l'hypothèse que les $n_i$ sont premiers entre eux deux à deux.

Dans le cas où les $n_i$ ne sont pas premiers entre eux, n est leur ppcm et le morphisme ci-dessus n'est qu'injectif. Il existe une solution au problème initial si et seulement si les données sont dans l'image, c'est-à-dire que le pgcd de $n_i$ et $n_j$ divise $\alpha_i-\alpha_j$ pour tout couple i,j.

Dans un anneau principal

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si r₁, ..., r_k sont des éléments de R qui sont premiers entre eux deux à deux, et r désigne le produit r₁...r_k, alors le morphisme d'anneaux

$\begin{matrix} f:&R/rR&\longrightarrow&R/r_1R\times\cdots\times R/r_kR\\ &x\;\mathrm{mod}\,rR&\longmapsto&(x\;\mathrm{mod}\,r_1R,\cdots,x\;\mathrm{mod}\,r_kR) \end{matrix}$

est un isomorphisme.

L'isomorphisme inverse peut être construit comme ceci. Pour chaque i, les éléments r_i et r / r_i sont premiers entre eux et par conséquent, il existe des éléments u_i et v_i dans R tels que

$u_i r_i + v_i\frac rr_i = 1$

Fixons e_i = v_i r / r_i. On a :

$e_i \equiv 1 \pmod{r_i} \quad\mathrm{et}\quad e_i \equiv 0 \pmod{r_j}$

pour j ≠ i.

Alors l'inverse de $f$ est le morphisme construit à l'aide des idempotents e_i (mod r) :

$\begin{matrix} g:&R/r_1R\times\cdots\times R/r_kR&\longrightarrow&R/rR\\ &(a_1\;\mathrm{mod}\,r_1R,\cdots,a_k\;\mathrm{mod}\,r_kR)&\longmapsto&\sum_{i=1}^ka_i e_i\;\mathrm{mod}\,rR~. \end{matrix}$

Exemple des polynômes

Un cas fréquent illustrant le paragraphe précédent est donné par l'anneau euclidien $R=K[X]$ des polynômes sur un corps $K$. Si x₀, x₁, ..., x_n sont n+1 éléments de $K$ distincts deux à deux, alors on peut prendre R_i = X - x_i . Les polynômes R_i sont premiers entre eux deux à deux, et le théorème des restes chinois s'applique. On prend pour E_i les polynômes interpolateurs de Lagrange, définis par : $E_i = {(X-x_0)(X-x_1)...(X-x_{i-1})(X-x_{i+1})...(X-x_n) \over(x_i-x_0)(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)}$.

Pour j différent de i, E_i est divisible par R_j, de sorte que E_i ≡ 0 modulo R_j. Par ailleurs, modulo R_i, X ≡ x_i, de sorte que E_i ≡ 1 modulo R_i.

Dire qu'un polynôme P est tel que P(x_i) = y_i pour tout i, est équivalent à dire que P ≡ y_i modulo R_i. Un tel polynôme P est donné par $P = \sum_{i=0}^n y_i E_i$ , ce qu'on peut vérifier par un calcul direct.

Résultat pour les anneaux généraux

Si R est un anneau et I₁, ..., I_k des idéaux bilatères de R deux à deux premiers entre eux (ce qui signife que I_i + I_j = R lorsque i ≠ j), on démontre (par récurrence sur k) que le morphisme

$\begin{matrix} R/(I_1\cap\cdots\cap I_k)&\longrightarrow&R/I_1\times\cdots\times R/I_k\\ x\;\mathrm{mod}\,I_1\cap\cdots\cap I_k&\longmapsto&(x\;\mathrm{mod}\,I_1,\cdots,x\;\mathrm{mod}\,I_k) \end{matrix}$

est un isomorphisme et que l'idéal intersection de ces idéaux est égal à la somme de tous leurs produits dans n'importe quel ordre :

$I_1\cap\cdots\cap I_k=\sum_{\sigma\in\mathfrak S_k}I_{\sigma(1)}\cdots I_{\sigma(k)}.$

Si l'anneau est commutatif, tous ces produits sont égaux et l'intersection des I_i est simplement égale à leur produit. Mais s'il ne l'est pas, pour deux idéaux bilatères I et J premiers entre eux, en général $I\cap J\ne IJ$, et on a seulement $I\cap J=IJ+JI$, d'où l'expression ci-dessus, avec une somme indexée par le groupe symétrique.

Utilisations

Le théorème des restes chinois est utilisé en particulier dans l'algorithme RSA en cryptographie, il intervient aussi dans L'algorithme de Silver-Pohlig-Hellman pour le calcul du logarithme discret.

Il permet de représenter de grands nombres entiers comme n-uplets de restes de divisions euclidiennes. Sous cette forme, des opérations comme l'addition ou la multiplication peuvent se faire en parallèle en temps constant (pas de propagation de retenue). Par contre, la comparaison ou la division ne sont pas triviales.

Voir aussi

Articles connexes

• Théorème de Bachet-Bézout
• Système couvrant

Liens externes

• (en) Chinese Remainder Theorem sur cut-the-knot
• Denis Daumas, Michel Guillemot, Olivier Keller, Raphaël Mizrahi, Maryvonne Spiesser, Le théorème des restes chinois, Textes, commentaires et activités pour l’arithmétique au lycée, sur le site CultureMath de l'ENS.