Théorème des restes chinois

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Crystal Clear app fonts.svg Cette page contient des caractères spéciaux ou non latins. Si certains caractères de cet article s’affichent mal (carrés vides, points d’interrogation…), consultez la page d’aide Unicode.

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[modifier | modifier le code]

La forme originale du théorème apparait sous forme de problème dans le livre de Sun Zi, le Sunzi suanjing (en), datant du IIIe siècle[1]. Il est repris par le mathématicien chinois Qin Jiushao dans son ouvrage le Shùshū Jiǔzhāng (« Traité mathématique en neuf chapitres (en) ») 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[2].

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 reste 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 en 1202 dans le Liber Abbaci de Fibonacci[3] 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.

Euler[4] s'est également intéressé à cette question, ainsi que Gauss[5].

Selon Ulrich Libbrecht (de)[6], la motivation de ce type de calcul chez les Chinois 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.[7], il s'agirait plus probablement de problèmes associés à des comptages par paquets, peut-être d'origine divinatoire.

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[modifier | modifier le code]

Théorème[modifier | modifier le code]

Soient n_1, …, n_k des entiers deux à deux premiers entre eux (ce qui veut dire pgcd (ni , nj) = 1 lorsque ij). Alors pour tous entiers a_1, …, a_k, il existe un entier x, unique modulo n = \prod_{i=1}^k n_i, 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 (v_i\, est l'inverse de \hat n_i modulo n_i). 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 ji.

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[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : Congruence linéaire.

Les systèmes de congruences peuvent être résolus même si les ni 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{{\rm PGCD}(n_i,n_j)} pour tous i et j. L'ensemble des solutions x forme alors une classe de congruence modulo le PPCM des ni.

Exemple : le système x ≡ –1 mod 4 et x ≡ –1 mod 6 équivaut à : x + 1 multiple de 4 et 6 c'est-à-dire de PPCM(4, 6) = 12, ou encore : x ≡ –1 mod 12.

Une méthode de résolution de tels systèmes est la méthode chinoise, qui consiste à se ramener à des modules premiers entre eux deux à deux (dans l'exemple ci-dessus : les modules 4 et 3). Une autre est la méthode des substitutions successives.

Interprétation mécanique[modifier | modifier le code]

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.

GeoplanPpcm.png

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-ièmes de l'unité, qui a une structure de groupe naturellement isomorphe à celle de ℤ/n.

Résultat pour les anneaux[modifier | modifier le code]

Dans les anneaux Z/nZ[modifier | modifier le code]

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:&\Z/n\Z&\longrightarrow& \Z/n_1\Z\times\cdots\times\Z/n_k\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 \Z/n\Z et \Z/n_1\Z\times\cdots\times\Z/n_k\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[modifier | modifier le code]

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si r1, …, rk sont des éléments de R qui sont premiers entre eux deux à deux, et r désigne le produit r1rk, 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 ri et r / ri sont premiers entre eux et par conséquent, il existe des éléments ui et vi dans R tels que

u_i r_i + v_i\frac rr_i = 1

Fixons ei = vi r / ri. On a :

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

pour ji.

Alors l'inverse de f est le morphisme construit à l'aide des idempotents ei (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[modifier | modifier le code]

Le théorème des restes chinois permet de résoudre explicitement tout système de congruences dans l'anneau euclidien R = K[X] des polynômes sur un corps K, c'est-à-dire tout système de la forme.

\forall i\in\{0,\ldots,n\}, P\equiv A_i\pmod{R_i}

où les données sont des polynômes Ri deux à deux premiers entre eux et des polynômes Ai, et l'inconnue est le polynôme P.

L'interpolation lagrangienne correspond au cas particulier où les Ri sont de la forme X – xi et les Ai sont constants, et fournit la solution P de degré ≤ n . Plus explicitement, si x0, x1, … , xn sont n + 1 éléments de K distincts deux à deux, on prend pour Ei 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, Ei est divisible par Rj, de sorte que Ei ≡ 0 modulo Rj. Par ailleurs, modulo Ri, X ≡ xi, de sorte que Ei ≡ 1 modulo Ri.

Pour n + 1 éléments quelconques y0, y1, … , yn de K, dire qu'un polynôme P est tel que P(xi) = yi pour tout i, est équivalent à dire que Pyi modulo Ri. 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[modifier | modifier le code]

Si R est un anneau et I1, …, Ik des idéaux bilatères de R deux à deux premiers entre eux (ce qui signife que Ii + Ij = R lorsque ij), on démontre (par récurrence sur k)[8] 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 Ii 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[9] 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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. Selon A. Zachariou, le théorème des restes chinois aurait été découvert antérieurement par les Grecs (Paulo Ribenboim, Nombres premiers et records, PUF, 1re éd., 1994, p. 24).
  2. (en) Man-Keung Siu, « “Algorithmic mathematics” and “Dialectics mathematics” », Proc. 2nd International Conference on the Teaching of Mathematics, 2002, p. 6.
  3. (la) Leonardus « Pisanus », Liber Abbaci, Tipogr. delle Scienze Matematiche e Fisiche, 1857, p. 304 (S. 311).
  4. (la) L. Euler, « Solutio problematis arithmetici de inveniendo numero, qui per datos numeros divisus relinquat data residua », Commentarii academiae scientiarum Petropolitanae, vol. 7, 1740, p. 46-66, ou bien Opera Omnia, Series 1, vol. 2, p. 18-32.
  5. (la) C. F. Gauss, Disquisitiones arithmeticae, 1801, p. 23, §32. Reproduction de la traduction Recherches arithmétiques, Gabay, 1989, p. 15.
  6. (en) Ulrich Libbrecht, Chinese Mathematics in the Thirteenth Century, 1973.
  7. Denis Daumas, Michel Guillemot, Olivier Keller, Raphaël Mizrahi et 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, § 1. Le problème des restes chinois : Questions sur ses origines.
  8. N. Bourbaki, Algèbre, chapitres 1 à 3, Springer, 2007 (ISBN 978-3-540-33849-9) p. A I.105 et 103.
  9. Un contre-exemple dans l'anneau des matrices triangulaires supérieures de taille 2 est proposé en exercice dans Bourbaki, op. cit., p. A I.151.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Chinese Remainder Theorem sur cut-the-knot