Le théorème des restes chinois est un résultat d'arithmétique traitant de résolution de systèmes de congruences. Ce résultat se généralise en théorie des anneaux. Ce théorème est utilisé en théorie des nombres.
La forme originale du théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...), contenue dans un livre du mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute...) chinois Qin Jiushao publié en 1247, est un résultat concernant les systèmes de congruences (voir arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la...) modulaire). Mais on trouve trace (TRACE est un télescope spatial de la NASA conçu pour étudier la connexion entre le...) d'un problème analogue dans le livre de Sun (Sun Microsystems (NASDAQ : SUNW) est un constructeur d'ordinateurs et un éditeur de...) Zi, le Sunzi suanjing datant du IIIe siècle :
On peut penser que les Chinois, férus de calculs astronomiques puissent être intéressés par des concordances de calendrier (Un calendrier est un système de repérage des dates en fonction du temps. Ces systèmes ont été...) et qu'ils aient été amenés très tôt à s'intéresser à des questions du type :
Si la question se pose alors qu'il reste 6 jours avant le solstice d'hiver (L'hiver est une des quatre saisons des zones tempérées.) et 3 jours avant la pleine lune (La Lune est l'unique satellite naturel de la Terre et le cinquième plus grand satellite du...), la question se traduit par:
La résolution proposée par Sun Zi pour le problème des soldats est la suivante :
Mais la solution n'explique qu'imparfaitement la méthode utilisée.
Enfin, il serait dommage de ne pas présenter ce problème concernant des pirates et un trésor, très fréquemment cité (La cité (latin civitas) est un mot désignant, dans l’Antiquité avant la...) pour illustrer le théorème des restes chinois :
L'arithmétique modulaire (En mathématiques et plus précisément en théorie algébrique des nombres,...) a rendu (Le rendu est un processus informatique calculant l'image 2D (équivalent d'une photographie)...) ce type de problème plus facile à résoudre.
Soient n1, ..., nk des entiers deux à deux premiers entre eux (ce qui veut dire pgcd (ni , nj) = 1 lorsque i ≠ j). Alors pour tous entiers a1, ..., ak, il existe un entier x, unique modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi...) et tel que
Une solution x peut être trouvée comme suit:
Pour chaque i, les entiers et
sont premiers entre eux, et en utilisant l'identité de Bézout, on peut trouver des entiers
et
tels que
. Si on pose
, alors nous avons
et
Une solution de ce système de congruences est par conséquent
Plus généralement, toutes les solutions x de ce système sont congrues modulo le produit n
Le problème des soldats se réduit à
on obtient alors
une solution pour x est alors
et les solutions sont tous les entiers congrus à 233 modulo 105, c'est-à-dire à 23 modulo 105.
Quelquefois, 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 : une solution x existe si et seulement si
pour tous i et j. Toutes les solutions x sont congrues modulo le PPCM des ni .
Exemple : résoudre le système
équivaut à résoudre le système
équivaut au système
Une solution est donc 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.
La résolution du système suivant :
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 (La roue est un organe ou pièce mécanique de forme circulaire tournant autour d'un axe passant par...) dentée comportant a dents s'engrène dans une tringle horizontale. Combien de dents doivent passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques...) pour que sa r-ième dent (Une dent est un organe enveloppé d'os, dur, blanchâtre, généralement...) vienne en coïncidence avec la s-ième dent d'une autre roue (La roue est un organe ou pièce mécanique de forme circulaire tournant autour d'un axe...) 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,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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 .
Le théorème chinois a également une version plus abstraite : si n1, ..., nk sont deux à deux premiers entre eux alors, en notant n le produit de ni, l'application
est un isomorphisme d'anneau.
Pour le montrer on remarque d'abord que les deux ensembles et
ont le même nombre d'éléments. Comme
est un morphisme d'anneau, il suffit donc de voir qu'il est injectif pour en déduire que c'est un isomorphisme. Pour voir cela il suffit de montrer que son noyau est réduit à 0 : si α = 0[ni] pour
, c’est-à-dire si α est un multiple de chaque ni, alors α = 0[n], c’est-à-dire α est un multiple du produit
. Ceci résulte de l'hypothèse que les ni sont premiers entre eux deux à deux.
Pour un anneau principal R, le théorème des restes chinois (Le théorème des restes chinois est un résultat d'arithmétique modulaire...) prend la forme suivante : Si u1, ..., uk sont les éléments de R qui sont premiers entre eux deux à deux, et u désigne le produit u1...uk, alors l'anneau R/uR et l'anneau produit R/u1R x ... x R/ukR sont isomorphes par l'isomorphisme
tel que
L'isomorphisme inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...) peut être construit comme ceci. Pour chaque i, les éléments ui et u/ui sont premiers entre eux, et par conséquent, il existe des éléments r et s dans R avec
Fixons ei = s u/ui. On a :
pour j ≠ i.
Alors l'inverse est la transformation
telle que
Une des formes les plus générales du théorème des restes chinois peut être formulée en termes d'anneau et d'idéal (En mathématiques, un idéal est une structure algébrique définie dans un anneau....) (à gauche ou à droite). Si R est un anneau et I1, ..., Ik des idéaux de R qui sont deux à deux premiers entre eux (ce qui signife que Ii + Ij = R lorsque i ≠ j), alors l'idéal produit I de ces idéaux est égal à leur intersection, et l'anneau quotient R/I est isomorphe à l'anneau produit R/I1 x R/I2 x ... x R/Ik via l'isomorphisme de R / I dans qui à
associe
.
Un cas fréquent illustrant le paragraphe précédent est donné par l'anneau des polynômes. Si x0, x1, ..., xn sont n+1 éléments de
distincts deux à deux, alors on peut prendre Ui = X - xi . Les polynômes Ui sont premiers entre eux deux à deux, et le théorème des restes chinois s'applique. On prend pour Ei les polynômes interpolateurs de Lagrange, définis par :
.
Pour j différent de i, Ei est divisible par Uj , de sorte que Ei ≡ 0 modulo Uj . Par ailleurs, modulo Ui , X ≡ xi , de sorte que Ei ≡ 1 modulo Ui .
Dire qu'un polynôme (Un polynôme, en mathématiques, est la combinaison linéaire des produits de...) P est tel que P(xi) = yi pour tout i, est équivalent à dire que P ≡ yi modulo Ui . Un tel polynôme P est donné par , ce qu'on peut vérifier par un calcul direct.
Le théorème des restes chinois est utilisé en particulier dans l'algorithme RSA en cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages...).
Il permet de représenter de grands nombres entiers comme n-uplets de restes de divisions euclidiennes. Sous cette forme, des operations comme l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la...) ou la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire...) peuvent se faire en parallèle en temps (Le temps est un concept développé par l'être humain pour appréhender le...) constant (pas de propagation de retenue). Par contre, la comparaison ou la division ne sont pas triviales.