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 vignette|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 Sunzi Suanjing, datant du 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, éd., 1994, ).. 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 comptant son armée Man-Keung Siu, « “Algorithmic mathematics” and “Dialectics mathematics” », Proc. International Conference on the Teaching of Mathematics, 2002, ..
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 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 Leonardus « Pisanus », Liber Abbaci, Tipogr. delle Scienze Matematiche e Fisiche, 1857, p. 304 (S. 311). 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 L. Euler, « Solutio problematis arithmetici de inveniendo numero, qui per datos numeros divisus relinquat data residua », Commentarii academiae scientiarum Petropolitanae, vol. 7, 1740, , ou bien Opera Omnia, Series 1, vol. 2, . s'est également intéressé à cette question, ainsi que Gauss C. F. Gauss, Disquisitiones arithmeticae, 1801, , §32. Reproduction de la traduction Recherches arithmétiques, Gabay, 1989, ..
Astronomie Selon Ulrich Libbrecht, Chinese Mathematics in the Thirteenth Century, 1973., 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.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., 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. 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..
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 des entiers deux à deux premiers entre eux, c'est-à-dire que lorsque . Alors pour tous entiers , il existe un entier , unique modulo , tel que
Algorithme Une solution peut être trouvée comme suit. Pour chaque , les entiers et sont premiers entre eux. D'après le théorème de Bachet-Bézout on peut calculer l'inverse de modulo . Pour cela, on peut utiliser l'algorithme d'Euclide étendu et obtenir des entiers et tels que . Si on pose , alors nous avons
et pour .
Une solution particulière de ce système de congruences est par conséquent
et les autres solutions sont les entiers congrus à modulo le produit .
Exemple L'exemple de Sun Zi, présenté plus haut dans la section histoire, se réduit à
on obtient alors
et , or donc et , or donc et , or donc
une solution pour est alors
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 ne sont pas premiers entre eux deux à deux. Le critère précis est le suivant :
Exemple : le système et équivaut à : multiple de et c'est-à-dire de , ou encore : .
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 La résolution du système , d'inconnue , passe par le calcul du PPCM de et .
Une roue dentée comportant dents s'engrène dans une autre roue dentée comportant elle dents. Combien de dents doivent passer pour que sa -ième dent vienne en coïncidence avec la -ième dent ?
Le PPCM des deux nombres et 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 . Il y a une solution si divise .
Fichier:GeoplanPpcm.png
Pour cet engrenage, pour , la solution est .
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
Dans les anneaux Z/nZ Le théorème chinois a également une version plus abstraite : si , …, sont deux à deux premiers entre eux alors, en notant le PPCM des , c'est-à-dire dans le cas présent le produit des , l'application (à valeurs dans l'anneau produit)
est un isomorphisme d'anneaux.
Par exemple, la table suivante compare et et chaque paire d'éléments de apparaît exactement une et seule fois : +x01234567891011121314x mod 3012012012012012x mod 5012340123401234 Pour le montrer, on remarque d'abord que les deux ensembles finis et ont le même nombre d'éléments. Comme 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 pour , c’est-à-dire si est un multiple de chaque , alors , c’est-à-dire est un multiple du produit . Ceci résulte de l'hypothèse que les sont premiers entre eux deux à deux.
Dans le cas où les ne sont pas deux à deux premiers entre eux, 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 et divise pour tout couple .
Dans un anneau principal
Pour un anneau principal , le théorème des restes chinois prend la forme suivante : Si sont des éléments de qui sont premiers entre eux deux à deux, et désigne le produit , alors le morphisme d'anneaux :
est un isomorphisme.
L'isomorphisme inverse peut être construit comme ceci. Pour chaque , les éléments et sont premiers entre eux et par conséquent, il existe des éléments et de tels que
Fixons On a :
pour .
Alors l'inverse de est le morphisme construit à l'aide des idempotents (modulo ) :
Exemple des polynômes
Le théorème des restes chinois permet de résoudre explicitement tout système de congruences dans l'anneau euclidien des polynômes sur un corps , c'est-à-dire tout système de la forme.
où les données sont des polynômes deux à deux premiers entre eux et des polynômes , et l'inconnue est le polynôme .
L'interpolation lagrangienne correspond au cas particulier où les sont de la forme et les sont constants, et fournit la solution de degré . Plus explicitement, si x, x, … , x sont n + 1 éléments de distincts deux à deux, on prend pour les polynômes interpolateurs de Lagrange, définis par :
Pour , est divisible par , de sorte que . Par ailleurs, , de sorte que .
Pour éléments quelconques de , dire qu'un polynôme est tel que pour tout , est équivalent à dire que . Un tel polynôme est donné par
ce qu'on peut vérifier par un calcul direct.
Subtilité dans les anneaux factoriels
La preuve du théorème des restes chinois repose sur l'existence d'une relation de Bézout. Dans les anneaux factoriels, il n'est pas toujours possible de faire le lien entre le fait que deux éléments soient premiers entre eux, et l'existence d'une relation de Bézout. Considérons par exemple l'anneau factoriel (il est factoriel car un anneau de polynômes sur un anneau factoriel est toujours factoriel, ce qui est un corollaire du lemme de Gauss sur le contenu).
On constate que et sont deux éléments de premiers entre eux. En effet, soit un diviseur commun. Le fait que se traduit par l'existence d'un tel que , ce qui implique que est constant, valant ou . Le fait que implique que ne peut pas valoir . Ainsi, et sont bien premiers entre eux.
On serait tenté de partir de cette dernière remarque pour appliquer le théorème chinois. Cela impliquerait, par exemple, l'existence d'un élément tel que et . La première relation donnerait un élément tel que donc est un nombre pair. Or, la seconde relation impliquerait que , ce qui est contradictoire.
La raison à cette contradiction est que les éléments et sont, certes, premiers entre eux (i.e., pas de facteur commun) mais les idéaux et ne sont pas premiers entre eux. En effet, leur somme n'est pas égale à . Plus précisément, . Cela prouve qu'il n'y a pas de relation de Bézout entre ces deux et .