Théorème des restes chinois

En mathématiques, 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, initialement établi 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

Fichier:Sun Tzu Chinese remainder theorem.svg

Exemple de Sun Zi : il y a 23 objets.

Exemple de Sun Zi

La forme originale du théorème apparait sous forme de problème dans le livre de Sun Zi, le Modèle:Lien, datant du Modèle:Lien siècleModèle:Vérification siècle<ref>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, Modèle:1re éd., 1994, Modèle:P.).</ref>. 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 ») 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 Modèle:Lien comptant son armée<ref>{{#invoke:Langue|indicationDeLangue}} Man-Keung Siu, « “Algorithmic mathematics” and “Dialectics mathematics” », Proc. Modèle:2d International Conference on the Teaching of Mathematics, 2002, Modèle:P..</ref>.

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 233 (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 (3×5×7) 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<ref>{{#invoke:Langue|indicationDeLangue}} Leonardus « Pisanus », Liber Abbaci, Tipogr. delle Scienze Matematiche e Fisiche, 1857, p. 304 (S. 311).</ref> 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. Le problème avait aussi été étudié par Ibn al-Haytham (Alhazen) – voir l'article Mathématiques arabes – dont Fibonacci a pu lire les œuvres.

Euler<ref>{{#invoke:Langue|indicationDeLangue}} L. Euler, « Solutio problematis arithmetici de inveniendo numero, qui per datos numeros divisus relinquat data residua », Commentarii academiae scientiarum Petropolitanae, vol. 7, 1740, Modèle:P., ou bien Opera Omnia, Series 1, vol. 2, Modèle:P..</ref> s'est également intéressé à cette question, ainsi que Gauss<ref>{{#invoke:Langue|indicationDeLangue}} C. F. Gauss, Disquisitiones arithmeticae, 1801, Modèle:P., §32. Reproduction de la traduction Recherches arithmétiques, Gabay, 1989, Modèle:P..</ref>.

Astronomie

Selon Modèle:Lien<ref>{{#invoke:Langue|indicationDeLangue}} Ulrich Libbrecht, Chinese Mathematics in the Thirteenth Century, 1973.</ref>, 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 ?

Comptage de paquets

Mais selon Daumas et al.<ref>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.</ref>, 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 ?

La réponse est 785. Les nombres 17, 11 et 6 étant premiers entre eux deux à deux, les solutions sont distantes d'un multiple de 1122 (17×11×6) ; par ailleurs 785 vérifie bien l'énoncé : 785 = 17×46 + 3 = 11×71 + 4 = 6×130 + 5. Il s'ensuit que 785 est bien le plus petit des nombres possibles<ref>Modèle:Ouvrage.</ref>.

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 <math>n_1</math>, …, <math>n_k</math> des entiers deux à deux premiers entre eux, c'est-à-dire que PGCD (n_i , n_j) = 1 lorsque i ≠ j. Alors pour tous entiers <math>a_1</math>, …, <math>a_k</math>, il existe un entier <math>x</math>, unique modulo <math>n = \prod_{i=1}^k n_i</math>, tel que

<math>

\begin{matrix} x \equiv a_1\pmod{n_1}\\ \ldots \\ x \equiv a_k\pmod{n_k}\\ \end{matrix} </math>

Algorithme

Une solution <math>x</math> peut être trouvée comme suit. Pour chaque i, les entiers <math>n_i</math> et <math>\hat{n}_i = \frac n{n_i} = n_1\ldots n_{i-1}n_{i+1}\ldots n_k</math> sont premiers entre eux. D'après le théorème de Bachet-Bézout on peut calculer l'inverse <math>v_i\,</math>de <math>\hat n_i</math> modulo <math>n_i</math>. Pour cela, on peut utiliser l'algorithme d'Euclide étendu et obtenir des entiers <math>u_i\,</math> et <math>v_i\,</math> tels que <math>u_in_i + v_i\hat n_i= 1</math>. Si on pose <math>e_i = v_i\hat n_i</math>, alors nous avons

<math>e_i \equiv 1\pmod{n_i}\,</math> et <math>e_i \equiv 0\pmod{n_j}\,</math> pour j ≠ i.

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

<math> x = \sum_{i=1}^k a_i e_i~,</math>

et les autres solutions sont les entiers congrus à <math>x</math> modulo le produit <math>n</math>.

Exemple

L'exemple de Sun Zi, présenté plus haut dans la section histoire, se réduit à

<math>x \equiv 2 \pmod{3}\, </math>

<math>x \equiv 3 \pmod{5}\, </math>

<math>x \equiv 2 \pmod{7} \,</math>

on obtient alors

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

une solution pour x est alors <math>x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233</math>

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

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 : Modèle:Énoncé \equiv 0 \mod p</math>, qui n'est autre qu'une équation linéaire modulo p, et a donc une solution <math>x</math> puisque p est premier avec <math>2x'</math>. Donc la congruence <math>x^2 - a \equiv 0</math> a lieu pour le modulo <math>m_1m_2 = p^{n+1}</math>, et pour tout modulo <math>p^k</math> en général.

• [[Résidu quadratique#Modulo une puissance d'un nombre premier|Tout entier Modèle:Mvar congru à 1 modulo 8 est résidu quadratique modulo 2ⁿ]], <math>n \in \mathbb N</math> (réciproque immédiate pour n > 2 et Modèle:Mvar impair).

La séparation <math>m_1 = 2^{n-1}</math> et <math>m_2 = 2</math> mène à une tautologie. Mais en observant que le résultat est immédiat pour <math>n\leq 3</math>, les carrés impairs étant toujours congrus à 1 modulo 8, on prend la séparation <math>m_1 = 2^{n-2}</math> et <math>m_2 = 4</math>, et on suppose le résultat vrai pour tout <math>n< N</math>, avec <math>N>3</math>. Soit donc <math>n = N</math>. L'hypothèse d'induction fournit une solution <math>x',</math> forcément impaire, de

<math> x'^2 - a \equiv 0 \mod 2^{n-1}</math>,

et c'est a plus forte raison une solution modulo <math>m_1</math>. On a d'autre part, avec les notations du lemme,

<math>Q(x) = 2^{n-2} x^2 + 2 x'x + {x'^2 - a\over 2^{n-2}} \equiv 2x'x + {x'^2 - a\over 2^{n-2}} \mod 4

\equiv 0 \iff x'x + {x'^2 - a\over 2^{n-1}} \equiv 0 \mod 2.</math> Et comme <math>x'</math> est impair, on a bien une solution <math>x</math> modulo <math>m_2</math> qui permet de conclure.

• Soit p un nombre premier impair, <math> a\in \mathbb Z</math> un nombre premier avec p, n un entier positif, et <math>f</math> une forme quadratique entière d'une ou plusieurs variables: sous forme matricielle, <math>f({\mathbf x}) = {1\over 2}{\mathbf x}^T M {\mathbf x}. </math> On suppose <math>\det(M)\not \equiv 0 \mod p</math>. Alors la congruence <math>f({\mathbf x}) \equiv a \mod p^n</math> est solvable si (et seulement si) la congruence <math>f({\mathbf x})\equiv a \mod p</math> l'est.

On prend <math>P({\mathbf x}) = {1\over 2} {\mathbf x^T}M{\mathbf x} - a</math>, et la séparation <math>m_1 = p^{n}</math>, <math>m_2 = p</math>. Supposons le résultat vrai pour n = N.

L'hypothèse d'induction fournit une solution <math>\mathbf x',</math> forcément non nulle, de <math> P({\mathbf x'}) \equiv 0 \mod p^{n},</math> et on a, avec les notations du lemme,

<math> Q({\mathbf x}) = {P({\mathbf x'})\over p^n} + {\mathbf x'^T} M {\mathbf x} +

{1\over 2}p^n{\mathbf x^T} M {\mathbf x} \equiv 0 \mod p,\quad \hbox{ou bien}\quad {\mathbf x'^T} M {\mathbf x} \equiv -{P({\mathbf x'})\over p^n} \mod p.</math> Cette dernière congruence, linéaire en <math>\mathbf x,</math> aura une solution si <math>{\mathbf x'}^T M\not \equiv 0</math> modulo p. Mais cela a lieu puisque <math>{\mathbf x'}\not \equiv 0</math> et que M est inversible modulo p. Donc la congruence proposée a une solution modulo <math>p^{n+1}</math>, et pour tous les moduli <math>p^k</math> en général.

Observons encore que le théorème des restes chinois peut être vu comme un corollaire de ce lemme, en réduisant la question par induction au cas de deux facteurs <math>m_1 := n_1</math> et <math>m_2:=n_2</math>, et en appliquant la méthode précédente au polynôme <math>P(X) = n_2(X-a_1) + n_1(X-a_2)</math> (avec les notations du début de l'article).

Utilisations

Le théorème des restes chinois est largement utilisé en arithmétique et en algèbre, notamment sous sa forme générale dans l'arithmétique des corps, que ce soit au cours de démonstrations théoriques aussi bien que dans des cas pratiques.

Dans le domaine de l'algorithmique, il est par exemple utilisé dans l'algorithme RSA en cryptographie, et il intervient aussi dans l'algorithme de Silver-Pohlig-Hellman pour le calcul du logarithme discret. Il intervient dans l'algorithme de test de primalité de Agrawal et Biswas, développé en 1999<ref>Modèle:Article</ref>.

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

Bibliographie

• Modèle:Ouvrage

• Modèle:Ouvrage

Liens externes

• {{#invoke:Langue|indicationDeLangue}} Modèle:Langue sur cut-the-knot