Voir la source de Théorème des restes chinois

{{Unicode}}

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 [[congruence sur les entiers|congruences]]. Ce résultat, initialement établi pour [[Anneau Z/nZ|ℤ/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|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 (mathématicien)|Sun Zi]], le ''{{Lien|langue=en|trad=The Mathematical Classic of Sunzi|fr=Classique mathématique de Sunzi|texte=Sunzi suanjing}}'', datant du {{IIIe 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]], {{1re}} éd., 1994, {{p.|24}}).</ref>. Il est repris par le [[Mathématiques chinoises|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 {{Lien|langue=en|fr=Han Xin}} comptant son armée<ref>{{en}} Man-Keung Siu, « [http://hkumath.hku.hk/~mks/ALGDIA.pdf “Algorithmic mathematics” and “Dialectics mathematics”] », ''Proc. {{2d}} International Conference on the Teaching of Mathematics'', 2002, {{p.|6}}.</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 <math>233\; (2\times 70+3\times 21+2\times 15)</math> 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 abaci|Liber Abbaci]]'' de [[Leonardo Fibonacci|Fibonacci]]<ref>{{la}} Leonardus « Pisanus », ''[http://www.mdz-nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de:bvb:12-bsb10525679-8 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.

[[Leonhard Euler|Euler]]<ref>{{la}} L. Euler, « [http://eulerarchive.maa.org/docs/originals/E036.pdf 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}}.</ref> s'est également intéressé à cette question, ainsi que [[Carl Friedrich Gauss|Gauss]]<ref>{{la}} C. F. Gauss, ''[https://gallica.bnf.fr/ark:/12148/bpt6k994003/f27.image.r=.langFR Disquisitiones arithmeticae]'', 1801, {{p.|23}}, §32. Reproduction de la traduction ''Recherches arithmétiques'', Gabay, 1989, {{p.|15}}.</ref>.

=== Astronomie ===
Selon {{Lien|langue=de|fr=Ulrich Libbrecht}}<ref>{{en}} Ulrich Libbrecht, ''Chinese Mathematics in the Thirteenth Century'', 1973.</ref>, la motivation de ce type de calcul chez les Chinois serait l'[[Astronomie chinoise|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, [http://culturemath.ens.fr/content/le-th%C3%A9or%C3%A8me-des-restes-chinois-textes-commentaires-et-activit%C3%A9s-pour-l%E2%80%99arithm%C3%A9tique-au-lyc%C3%A9e Le théorème des restes chinois], Textes, commentaires et activités pour l’arithmétique au lycée, sur le [http://www.math.ens.fr/culturemath/index.html site CultureMath] de l'ENS, [http://www.math.ens.fr/culturemath/materiaux/irem-toulouse11/questions-sur-les-origines.html#r3 § 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>{{Ouvrage|titre=Arithmétiques|auteur=Louis Frécon|éditeur=Publibook|année=2016|url={{Google Livres|EZU2DQAAQBAJ|page=121}}|page=121}}.</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, \ldots, n_k</math> des entiers deux à deux [[premiers entre eux]], c'est-à-dire que [[Plus grand commun diviseur de nombres entiers|<math>\text{PGCD}</math>]]<math>(n_i,n_j)=1</math> lorsque <math>i\ne j</math>. Alors pour tous entiers <math>a_1,\ldots,a_k</math>, il existe un entier <math>x</math>, unique [[congruence sur les entiers|modulo]] <math>n = \prod_{i=1}^k n_i</math>, tel que

:<math>
\begin{cases}
x \equiv a_1\pmod{n_1}\\
\quad \vdots \\
x \equiv a_k\pmod{n_k}\\
\end{cases}
</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>

<!---  x % 3 == 2 % 3 &&
  x % 4 == 3 % 4 &&
  x % 5 == 2 % 5 -->
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 <math>x</math> 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 ===
{{Article détaillé|Congruence linéaire}}

Les systèmes de congruences peuvent être résolus même si les ''n<sub>i</sub>'' ne sont pas premiers entre eux deux à deux. Le critère précis est le suivant :
{{Énoncé|une solution ''x'' existe si et seulement si <math>a_i \equiv a_j \pmod{{\rm PGCD}(n_i,n_j)}</math> pour tous ''i'' et ''j''. L'ensemble des solutions ''x'' forme alors une classe de congruence modulo le [[Plus petit commun multiple|PPCM]] des ''n<sub>i</sub>''.
}}
Exemple : le système <math>x\equiv -1\; [4]</math> et <math>x\equiv -1\; [6]</math> équivaut à : <math>x+1</math> multiple de <math>4</math> et <math>6</math> c'est-à-dire de <math>\text{PPCM}(4,6)=12</math>, ou encore : <math>x\equiv -1 \pmod {12}</math>

Une méthode de résolution de tels systèmes est la [[Congruence linéaire#Méthode chinoise|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 [[Congruence linéaire#Méthode des substitutions successives|méthode des substitutions successives]].

=== Interprétation mécanique ===
La résolution du système <math>
  \left\{\begin{array}{l}
    x\equiv r \pmod a \\
  x\equiv s \pmod b
\end{array}\right.</math>  &#x202F;, d'[[inconnue (mathématiques)|inconnue]] <math>x</math> , passe par le calcul du PPCM de <math>a</math> et <math>b</math>.

Une roue dentée comportant <math>a</math> dents s'engrène dans une autre roue dentée comportant elle <math>b</math> dents. Combien de dents doivent passer pour que sa <math>r</math>-ième dent vienne en coïncidence avec la <math>s</math>-ième dent ?

Le PPCM des deux nombres <math>a</math> et <math>b</math> 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 <math>[1,\rm{PPCM}(a,b)]</math>. Il y a une solution si PGCD(''a'', ''b'') divise ''r – s'' .

[[Fichier:GeoplanPpcm.png]]

Pour cet engrenage, 
<math>
\begin{cases}
x\equiv 4\pmod {15}\\
x\equiv 10\pmod {12}
\end{cases}, \text{PPCM}(12,15)=60
</math> pour <math>x\in [1, 60]</math> , la solution est <math>x=34</math>.

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

== Résultat pour les anneaux ==

=== Dans les [[Anneau Z/nZ|anneaux Z/''n''Z]] ===
Le théorème chinois a également une version plus abstraite : si {{math|''n''{{ind|1}}}}, …, {{math|''n{{ind|k}}''}} sont deux à deux premiers entre eux alors, en notant {{math|''n''}} le [[Plus petit commun multiple|PPCM]] des {{math|''n{{ind|i}}''}}, c'est-à-dire dans le cas présent le produit des {{math|''n{{ind|i}}''}}, l'application (à valeurs dans l'[[Produit d'anneaux|anneau produit]])
<center>
<math>
\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}
</math>
</center>
est un [[Morphisme d'anneaux#Composition de morphismes|isomorphisme d'anneaux]].

Par exemple, la table suivante<ref>{{Ouvrage|langue=en|auteur1=|prénom1=Dexter C.|nom1=Kozen|titre=Theory of Computation|passage=p. 86, Supplementary Lecture B, Chinese Remaindering|éditeur=Springer-Verlag|collection=Texts in Computer Science|date=2006|isbn=9781846282973|lire en ligne=https://www.springer.com/gp/book/9781846282973|consulté le=2019-07-09}}</ref> compare <math>\Z/15\Z</math> et <math>\Z/3\Z \times \Z/5\Z</math> et chaque paire d'éléments de <math>\Z/3\Z \times \Z/5\Z</math> apparaît exactement une et seule fois :
{| class="wikitable"
|+
!x
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
!11
!12
!13
!14
|-
|x mod 3
|0
|1
|2
|0
|1
|2
|0
|1
|2
|0
|1
|2
|0
|1
|2
|-
|x mod 5
|0
|1
|2
|3
|4
|0
|1
|2
|3
|4
|0
|1
|2
|3
|4
|}
Pour le montrer, on remarque d'abord que les deux ensembles finis <math>\Z/n\Z</math> et <math>\Z/n_1\Z\times\cdots\times\Z/n_k\Z</math> ont le même nombre d'éléments. Comme <math>\phi</math> 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 <math>\alpha\equiv0\mod{n_i}</math> pour <math>i=1, \dots, k</math>, c’est-à-dire si <math>\alpha</math> est un multiple de chaque {{math|''n{{ind|i}}''}}, alors <math>\alpha\equiv0\mod n</math>, c’est-à-dire <math>\alpha</math> est un multiple du produit <math>n_1,\ldots,n_k</math>. Ceci résulte de l'hypothèse que les <math>n_i</math> sont premiers entre eux deux à deux.

Dans le [[#Généralisation à des nombres non premiers entre eux|cas où les {{math|''n{{ind|i}}''}} 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 <math>n_i</math> et <math>n_j</math> divise <math>a_i-a_j</math> pour tout couple <math>(i,j)</math>.

=== Dans un anneau principal ===

Pour un [[anneau principal]] ''R'', le théorème des restes chinois prend la forme suivante : Si ''r''<sub>1</sub>, …, ''r<sub>k</sub>'' sont des éléments de ''R'' qui sont [[Primalité dans un anneau#Éléments premiers entre eux et élément irréductible|premiers entre eux]] deux à deux, et ''r'' désigne le produit ''r''<sub>1</sub>…''r<sub>k</sub>'', alors le morphisme d'anneaux
<center>
<math>
\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}
</math>
</center>
est un isomorphisme.

L'isomorphisme inverse peut être construit comme ceci. Pour chaque ''i'', les éléments ''r<sub>i</sub>'' et ''r'' / ''r<sub>i</sub>'' sont premiers entre eux et par conséquent, il existe des éléments ''u<sub>i</sub>'' et ''v<sub>i</sub>'' dans ''R'' tels que
:<math>u_i r_i + v_i\frac rr_i = 1 </math>

Fixons ''e<sub>i</sub>'' = ''v<sub>i</sub> r'' / ''r<sub>i</sub>''. On a :
:<math>e_i \equiv 1 \pmod{r_i} \quad\mathrm{et}\quad
e_i \equiv 0 \pmod{r_j}</math>

pour ''j'' ≠ ''i''.

Alors l'inverse de ''{{math|f}} ''est le morphisme construit à l'aide des [[idempotent]]s ''e{{ind|i}}'' (mod ''r'') :
<center>
<math>
\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}
</math>
</center>

==== 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]] ''R ''= ''K''[''X''] des [[Polynôme#Coefficients dans un corps commutatif|polynômes sur un corps]] ''K'', c'est-à-dire tout système de la forme.

{{Retrait|<math>\forall i\in\{0,\ldots,n\}, P\equiv A_i\pmod{R_i}</math>}}

où les données sont des polynômes ''R{{ind|i}} ''deux à deux premiers entre eux et des polynômes ''A{{ind|i}}'', et l'inconnue est le polynôme ''P''.

L'interpolation lagrangienne correspond au cas particulier où les ''R{{ind|i}} ''sont de la forme ''X – x{{ind|i}} ''et les ''A{{ind|i}} ''sont [[Polynôme constant|constants]], et fournit la solution ''P ''de degré ≤ ''n ''. Plus explicitement, si ''x''{{ind|0}}, ''x''{{ind|1}}, … , ''x{{ind|n}}'' sont ''n ''+ 1 éléments de ''K ''distincts deux à deux, on prend pour ''E<sub>i</sub> ''les [[Interpolation lagrangienne|polynômes interpolateurs de Lagrange]], définis par :
{{Retrait|<math>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)}.</math>}}
Pour ''j'' différent de ''i'', ''E<sub>i</sub>'' est divisible par ''R<sub>j</sub>'', de sorte que ''E<sub>i</sub>'' ≡ 0 modulo ''R<sub>j</sub>''. Par ailleurs, modulo ''R<sub>i</sub>'', ''X ≡ x<sub>i</sub>'', de sorte que ''E<sub>i</sub>'' ≡ 1 modulo ''R<sub>i</sub>''.

Pour ''n ''+ 1 éléments quelconques ''y''{{ind|0}}, ''y''{{ind|1}}, … , ''y{{ind|n}} ''de ''K'', dire qu'un polynôme ''P ''est tel que ''P''(''x''<sub>''i''</sub>) = ''y''<sub>''i''</sub> pour tout ''i'', est équivalent à dire que ''P ''≡ ''y''<sub>''i''</sub> modulo ''R<sub>i</sub>''. Un tel polynôme ''P ''est donné par
{{Retrait|<math>P = \sum_{i=0}^n y_i E_i,</math>}}
ce qu'on peut vérifier par un calcul direct.

=== Subtilité dans les anneaux factoriels ===

La preuve du théorème chinois repose sur l'existence d'une relation de Bézout. Dans les [[anneau factoriel|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 <math>\mathbb Z[X]</math> (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 (polynômes)|lemme de Gauss sur le contenu]]).

On constate que <math>2</math> et <math>X</math> sont deux éléments de <math>\mathbb Z[X]</math> premiers entre eux. En effet, soit <math>Q</math> un diviseur commun. Le fait que <math>Q\mid 2</math> se traduit par l'existence d'un <math>R\in \mathbb Z[X]</math> tel que <math>QR=2</math>, ce qui implique que <math>Q</math> est constant, valant <math>\pm 1</math> ou <math>\pm 2</math>. Le fait que <math>Q\mid X</math> implique que <math>Q</math> ne peut pas valoir <math>\pm 2</math>. Ainsi, <math>2</math> et <math>X</math> 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 <math>P\in\mathbb Z[X]</math> tel que <math>P\equiv 0 [2]</math> et <math>P\equiv 1[X]</math>. La première relation donnerait un élément <math>Q\in\mathbb Z[X]</math> tel que <math>P=2Q</math> donc <math>P(0)</math> est un nombre pair. Or, la seconde relation impliquerait que <math>P(0)=1</math>, ce qui est contradictoire.

La raison à cette contradiction est que les éléments <math>2</math> et <math>X</math> sont, certes, premiers entre eux (i.e., pas de facteur commun) mais les idéaux <math>(2)</math> et <math>(X)</math> ne sont pas premiers entre eux. En effet, leur somme n'est pas égale à <math>\mathbb Z[X]</math>. Plus précisément, <math>(2)+(X)=\{XP+2n\mid P\in\mathbb Z[X],n\in\mathbb{Z}\}</math>. Cela prouve qu'il n'y a pas de relation de Bézout entre ces deux <math>2</math> et <math>X</math>.

Remarque : on pourrait remplacer le nombre <math>2</math> par n'importe quel nombre entier différent de 0, 1 ou -1, et ce contre-exemple fonctionnerait verbatim.

=== Dans les corps munis de valuations indépendantes ===
Le théorème des restes chinois s'étend de plusieurs façons aux corps munis d'un certain nombre de [[valuation|valuations]] indépendantes<ref name=Jarden>{{Chapitre|langue=en|auteur={{Lien|Moshe Jarden}}|titre=Intersections of local algebraic extensions of a Hilbertian field|titre ouvrage=Generators and Relations in Groups and Geometries|auteurs ouvrage=A. Barlotti et al.|collection=NATO ASI Series C|numéro dans collection=333|page=343-405|éditeur=Kluwer|lieu=Dordrecht|date=1991|url=http://www.math.tau.ac.il/~jarden/Articles/paper56.pdf}}, p. 17 du pdf, prop. 4.4, 4.5 et rmk 4.6.</ref>{{,}}<ref>{{Ouvrage|langue=en|prénom1=J. W. S.|nom1=Cassels|lien auteur1=John Cassels|nom2=[[Albrecht Fröhlich|A. Fröhlich]]|titre=Algebraic Number Theory|éditeur=Academic Press|année=1967|pages totales=366|isbn=978-0-9502734-2-6|page=48}}.</ref>, tels que les [[anneau factoriel|anneaux factoriels]] (et ''a fortiori'' principaux), les [[anneau de Dedekind|anneaux de Dedekind]] etc.
On le trouve alors sous le nom de « {{Lien|trad=Adele ring#Approximation theorems|théorème d'approximation faible}} » :

''Soient <math>v_1,v_2,\ldots,v_n</math> des [[valuation#valuations discrètes|valuations discrètes]] indépendantes d'un [[Corps (mathématiques)|corps]] <math>K</math> , <math>a_1,a_2,\ldots,a_n</math> des éléments de <math>K</math>, et <math>k_1,k_2,\ldots,k_n</math> des entiers relatifs. Alors il existe <math>x\in K</math> tel que <math>v_i(x-a_i)=k_i</math> pour tout <math>i</math>.

Le théorème reste vrai pour les valuations non discrètes, en remplaçant les <math>k_i</math> par des éléments du groupe des valeurs des <math>v_i</math><ref name=Jarden/>.

Le théorème ne suppose pas que les ''a{{ind|i}}'' soient éléments d'un anneau, ni que les ''k{{ind|i}}'' soient positifs. Par contre, même si les valuations sont issues d'un anneau (intègre) ''A'', ''x'' ne peut être supposé élément de ''A''.

Voyons ce que le théorème signifie pour les rationnels en général lorsque les ''k{{ind|i}}'' sont positifs, les valuations en jeu étant les valuations ''p'' adiques.
Si ''q'' dénote un [[nombre rationnel]], convenons ici, par homologie avec le cas entier, que ''q'' est multiple d'un entier ''n'' si le [[numérateur]] de ''q'' l'est, et si le dénominateur de ''q'' est premier avec ''n''.
Convenons encore de noter <math>q_1=q_2 \; [n]</math> si <math>q_1-q_2</math> est multiple de <math>n</math> (on peut facilement vérifier que les principes de base des congruences fonctionnent encore pour cette dȩfinition étendue, à quelques adaptations près).

Le théorème d'approximation faible implique<ref>Les ''n{{ind|i}}'' sont produits de puissances ''p{{ind|i,j}}{{exp|c{{ind|i,j}}}}'' où les ''p{{ind|i,j}}'' sont des facteurs premiers distincts. En appliquant le thm. d'approximation faible aux valuations ''p{{ind|i}}''-adiques ''v{{ind|i,j}}'' correspondantes, on obtient un ''x'' tel que ''v{{ind|i,j}}''(''x - q{{ind|i}}'') = ''c{{ind|i,j}}''. Donc ''x - q{{ind|i}}'' est multiple de ''p{{ind|i,j}}{{exp|c{{ind|i,j}}}}'' pour tout ''j'', et donc de ''n{{ind|i}}''.</ref> alors que si ''n{{ind|1}}'', ''n{{ind|2}}'', ... ''n{{ind|r}}'' sont ''r'' entiers premiers deux à deux, et ''q{{ind|1}}'', ''q{{ind|2}}'', ... ''q{{ind|r}}'' sont ''r'' rationels, alors il existe un rationnel ''q'' tel que ''q'' = ''q{{ind|i}}'' mod ''n{{ind|i}}'' pour tout ''i'' (ce qui est loin de se déduire trivialement du théorème des restes chinois<ref>Preuve directe: notons ''q{{ind|i}}'' = {{nobr|''a{{ind|i}} / b{{ind|i}}''}}, et ''c{{ind|i,j}}'' = {{nobr|P.G.C.D.(''n{{ind|i}}, b{{ind|j}}'')}}. Pour tout ''i'', le théorème chinois fournit des nombres entiers ''e{{ind|i}}'' tels que ''e{{ind|i}}'' = {{nobr|1 mod ''n{{ind|i}}''}} et ''e{{ind|i}}'' = {{nobr|0 mod ''n{{ind|k}}c{{ind|k,i}}''}}, pour tout ''k'' ≠ ''i''. Alors ''q'' = {{nobr|∑{{ind|''i''}}''q{{ind|i}} e{{ind|i}}''}} satisfait à la question.</ref>).

On va maintenant faire voir que ce théorème implique le théorème des restes chinois dans <math>\mathbb Z</math>, et même dans les anneaux principaux. En fait, il est même un peu plus général, car il fournit un élément ''x'' de valuation p{{ind|i}}-adique exactement égale aux ''k{{ind|i}}''.

Supposons donc que ''A'' soit un anneau principal, de corps de fractions ''K''. Avec les notations du début de l'article, si les ''n{{ind|i}}'' sont décomposés en produit de puissances de facteurs premiers ''p{{ind|i}}{{ind|j}}{{exp|c{{ind|i,j}}}}'', on voit facilement, en répétant éventuellement les ''a{{ind|i}}'' correspondants, qu'il suffit de supposer que ''n{{ind|i}}'' est une puissance d'un certain élément premier ''p{{ind|i}}'', disons ''p{{ind|i}}{{exp|c{{ind|i}}}}''.

En notant ''v{{ind|i}}'' les valuations ''p{{ind|i}}''-adiques correspondantes, le théorème d'approximation faible dit qu'il existe un élément ''x'' de ''K'' tel que {{nobr|''v{{ind|i}}''(''x'' - ''a{{ind|i}}'') {{=}} ''c{{ind|i}}''}} pour tout ''i''. Notons ''x'' = ''r''/''s'', où ''r'' et ''s'' sont des éléments de ''A'' premiers entre eux. On a donc 
:<math> {r\over s}- a_i = p_i^{c_i} q, \ q\in K,</math>
les numérateurs et dénominateurs de ''q'' n'étant pas multiples de ''p{{ind|i}}''. Multiplions cette équation par ''s'', puis regardons la modulo ''p{{ind|i}}{{exp|c{{ind|i}}}}'' :
:<math>sa_i = r \ {\rm mod}\ p_i^{c_i}.</math>   
Cela implique que ''s'' n'est pas multiple de ''p{{ind|i}}'' pour tout ''i'', puisque ''r'' est premier avec ''s''. Il existe donc ''t'' dans ''A'' tel que <math>st = 1 \ {\rm mod}\ p_1^{c_1}\cdots p_n^{c_n}</math>.
En multipliant la congruence précédente par ''t'', on obtient <math>a_i = rt \ {\rm mod}\ p_i^{c_i}</math> pour tout ''i''; donc ''rt'' satisfait aux conditions du théorème des restes chinois.

Observons pour finir que le théorème d'approximation faible n'est pas englobé par le théorème chinois dans les anneaux généraux, exposé dans la section suivante, car les [[Idéal premier|idéaux premiers]] associés aux valuations ne réalisent pas nécessairement la condition de Bezout; un exemple simple est l'anneau factoriel <math>\mathbb Z[X]</math>, où l'on a les ideaux premiers <math><p></math> et <math><X></math>, ''p'' un nombre premier quelconque, mais <math><p> + <X>\not = \mathbb Z[X]</math>.

=== Résultat pour les anneaux généraux ===

Si ''R'' est un [[anneau unitaire|anneau]] et ''I''<sub>1</sub>, …, ''I<sub>k</sub>'' des [[idéal bilatère|idéaux bilatères]] de ''R'' deux à deux [[Nombres premiers entre eux#Généralisation|premiers entre eux]] (ce qui signifie que ''I<sub>i</sub>'' + ''I<sub>j</sub>'' = ''R'' lorsque ''i'' ≠ ''j''), on démontre (par récurrence sur ''k'')<ref>{{Ouvrage|auteur=[[N. Bourbaki]]|titre=[[Éléments de mathématique|Algèbre]], chapitres 1 à 3|éditeur=[[Springer Verlag|Springer]]|date=2007|isbn=978-3-540-33849-9}}, p. A I.105 et 103.</ref> que le morphisme
<center>
<math>
\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}
</math>
</center>
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 :
<center><math>I_1\cap\cdots\cap I_k=\sum_{\sigma\in\mathfrak S_k}I_{\sigma(1)}\cdots I_{\sigma(k)}.</math></center>
Si l'anneau est commutatif, tous ces produits sont égaux et l'intersection des ''I<sub>i</sub>'' 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<ref>Un [[contre-exemple]] dans l'anneau des [[Matrice triangulaire|matrices triangulaires]] supérieures de taille 2 est proposé en exercice dans {{Harvsp|Bourbaki|2007}}, p. A I.151.</ref>  <math>I\cap J\ne IJ</math>, et l'on a seulement <math>I\cap J=IJ+JI</math>, d'où l'expression ci-dessus, avec une somme indexée par le [[groupe symétrique]].

Si ''R'' est un [[anneau commutatif]] général, rien n'autorise à supposer que les idéaux sont co-premiers, même si ''R'' est intègre et que ces idéaux sont premiers. Cependant, on peut se demander si le théorème chinois généralisé ({{c.-à-d.}} qui ne suppose pas les ''n{{ind|i}}'' premiers entre eux, mais impose des conditions sur les ''a{{ind|i}}'') aurait lieu.

C'est justement le cas des {{Lien|trad=Prüfer domain|Anneau de Prüfer|texte=anneaux de Prüfer}} et en réalité, cette propriété les caractérise. Plus précisément<ref>{{Lien web|lang=en|auteur=Pete L. Clark|titre=Commutative Algebra|date=2015|url=http://alpha.math.uga.edu/~pete/integral2015.pdf|site=alpha.math.[[Université de Géorgie|uga.edu]]|page=345-348}}, Th. 21.1 et 21.6.</ref>{{,}}<ref>{{Ouvrage|lang=en|auteur={{Lien|László Fuchs}}|auteur2=Luigi Salce|titre=Modules over Non-Noetherian Domains|éditeur=[[American Mathematical Society|AMS]]|date=2001|numéro chapitre=III|chap=Prüfer Domains|url={{Google Livres|gK_yBwAAQBAJ|page=91}}|page=91-96}}, Th. 1.1 + ex. 1.9 et 1.10.</ref><!--Voir aussi https://math.stackexchange.com/questions/145207/the-chinese-remainder-theorem-and-distributive-lattices-->, pour qu'un anneau commutatif intègre soit de Prüfer, il faut et il suffit qu'un système de congruences <math>x = x_i {\ \rm mod\ } I_i</math> admette des solutions dès que <math>x_i\equiv x_j {\rm \ mod\ } (I_i + I_j).</math>

Évidemment, si les idéaux ''I{{ind|i}}'' sont co-premiers, l'idéal ''I{{ind|i}} + I{{ind|j}}'' est ''R'' tout entier, donc la condition sur ''x{{ind|i}}'' et ''x{{ind|j}}'' est toujours vérifiée, et le système de congruence a une solution ''x''. On retrouve bien le théorème chinois, tel qu'exposé au début de cette section.

== Applications ==
Des applications du théorème des restes chinois se rencontrent dans la branche diophantienne de la théorie des congruences.

Le théorème suivant peut être vu soit comme une application du théorème des restes chinois, soit comme une généralisation de ce théorème.

Soit <math>P_i\left(x_1,x_2,\ldots,x_n\right)\equiv 0 \; \left[m_i\right]</math> avec <math>i\in \{1, 2, \ldots, k\}</math> un système de <math>k</math> congruences, où les <math>P_i</math> sont des polynômes de <math>n</math> variables, et où les modules <math>m_i</math> sont premiers deux à deux. Alors ces congruences sont conjointement solvables si et seulement si chacune d'entre elles est solvable séparément; plus précisément, si ''m'' est le produit des modules <math>m_i</math>, chaque n-uplet <math>(x_1,x_2,\ldots,x_n)</math> où  <math>x_i</math> est une solution de la i-ème congruence, détermine bijectivement un n-uplet 
{{nobr|(''y{{ind|1}}'', ''y{{ind|2}}'', ... , ''y{{ind|n}}'')}} modulo ''m'' satisfaisant toutes les congruences à la fois.

De plus, si l'on convient d'appeler "primitive" une solution {{nobr|(''x{{ind|1}}'', ''x{{ind|2}}'', ... , ''x{{ind|n}}'')}} d'une congruence telle que chacun des ''x{{ind|i}}'' soit premier avec le module ''m{{ind|i}}'', alors le théorème précédent reste vrai si on le restreint aux solutions primitives: 
Les congruences sont conjointement primitivement solvables si et seulement si chacune d'entre elles l'est séparément, et il y a [[bijection]] entre les n-uplets de solutions primitives modulo ''m{{ind|i}}'', et ceux de solutions primitives conjointes modulo ''m''.

La preuve de ce théorème est simple : une solution conjointe induit évidemment une solution pour chaque équation séparément, et inversement, à partir de telles solutions, on reconstruit une solution conjointe avec le théorème des restes chinois.

Évidemment, si <math>P_i(x)=x-a_i</math>, on retrouve le théorèmes des restes chinois.

Un autre théorème notoire est le suivant :

Soit <math>P(x_1,x_2,\ldots,x_n)\equiv 0 \; [m]</math> une congruence, où <math>P</math> est un polynôme de <math>n</math> variables, et supposons que <math>m</math> soit le produit de <math>k</math> modules <math>m_i</math> premiers deux à deux.
Alors cette congruence est solvable (resp. primitivement solvable) modulo ''m'' si et seulement si elle est solvable (resp. primitivement solvable) modulo chaque ''m{{ind|i}}''. À nouveau, il y a bijection entre les solutions de la première congruence modulo ''m'' et les k-uplets de solutions de congruences modulo chaque ''m{{ind|i}}''. La preuve est similaire à celle du théorème précédent.

Grâce à ce dernier théorème, la solution d'une congruence modulo ''m'' se réduit a celle des solutions modulo chacune des puissances maximales de facteurs premiers {{nobr|composant ''m''.}}

Parmi les nombreuses applications du théorème des restes chinois à la théorie des nombres, citons encore la démonstration de la multiplicativité de l'[[indicatrice d'Euler]].

=== Une méthode connexe ===
On a vu qu'une des applications majeures du théorème des restes chinois résidait dans le fait que la résolution d'une congruence modulo un nombre ''m'', produit de deux nombres ''m''{{ind|1}} et ''m''{{ind|2}}, se réduisait à la résolution de cette même congruence modulo ''m''{{ind|1}} et ''m''{{ind|2}}, lorsque ''m''{{ind|1}} et ''m''{{ind|2}} sont premiers entre eux. Typiquement, les ''m{{ind|i}}'' sont des puissances de nombres premiers, le théorème chinois étant poussé le plus loin possible.
Cela simplifie déjà considérablement les problèmes théoriques et pratiques, mais comment réduire la question plus encore ?
La technique suivante est déjà utilisée par Gauss dans les ''[[Disquisitiones arithmeticae]]''. Pratiquée avec habileté, le plus souvent par le biais d'une [[descente infinie]], elle permet une analyse fine des cas où les nombres ''m''{{ind|1}} et ''m''{{ind|2}} ne sont pas premiers entre eux, et de ramener finalement la question aux moduli premiers.

Soit <math>P(x_1, x_2, \ldots x_n) \equiv 0 \mod m</math> une congruence, où <math>P</math> est un polynôme de ''n'' variables, et ''m'' est le produit de ''m''{{ind|1}} et ''m''{{ind|2}}, non nécessairement premiers entre eux.
La résolution de cette congruence équivaut à la résolution ''successive'' de
<math>P(x'_1, x'_2, \ldots, x'_n) \equiv 0 \mod m_1</math> puis de 
<math>Q(x''_1, x''_2, \ldots, x''_n) \equiv 0 \mod m_2</math>
où le polynôme ''Q'' à coefficients entiers est égal à
:<math>Q(X_1, \ldots, X_n) = {{1\over m_1}} P(m_1X_1 + x'_1,\ldots, m_1X_n + x'_n)</math>.
L'ensemble des solutions est alors <math>\{(x_i) = (x'_i + m_1 x''_i),\ (x'_i)\in S_1,\ (x''_i)\in S_2\},</math>
où <math>S_1</math> et <math>S_2</math> sont les ensembles de solutions des congruences ci-dessus resp.

{{Démonstration/début|titre=Démonstration et exemples}}
Si la proposée a une solution <math>x_i</math> modulo ''m'', alors cette solution est évidemment une solution modulo ''m''{{ind|1}}. On peut donc poser <math>x_i = x'_i + m_1 x''_i </math>, où <math>(x'_i)</math> est une solution de la proposée modulo ''m''{{ind|1}}, et <math>x''_i</math> est un nombre entier déterminé par <math>x'_i</math> et <math>x_i</math>.
Ainsi, les <math>x''_i</math> vérifient <math> R(x''_i) = 0\mod m,</math> avec <math>R = P(x'_i + m_1 X_i).</math> Mais il est facile de voir que tous les coefficients du polynôme ''R'' sont multiples de ''m''{{ind|1}}. On peut donc simplifier cette dernière congruence par ''m''{{ind|1}}, ce qui donne <math>Q(x''_i) = 0\mod m_2</math> (notations de l'énoncé).

Réciproquement, supposons qu'il existe une solution de la congruence <math> P(x_i) = 0 \mod m_1,</math> et une autre de la congruence <math>Q(x''_i) = 0 \mod m_2,</math>
''Q'' étant défini à partir de ''P'' et <math>(x_i)</math> comme précédemment.
Alors en remontant l'argument précédent, on voit que <math>(x_i = x'_i + m_1 x''_i)</math> est une solution de la proposée.

'''Exemples :'''

*Donnons-nous un nombre premier impair ''p'', un entier positif ''n'', et un nombre {{mvar|a}} premier avec ''p''. Soit à démontrer (sans utiliser de racine primitive modulo ''p'') que [[Résidu quadratique#Modulo une puissance d'un nombre premier|{{mvar|a}} est résidu quadratique modulo ''p{{exp|n}}'' si c'est un résidu quadratique modulo ''p'']] (la réciproque est triviale).

On suppose par récurrence le résultat vrai pour ''n = N'' > 0, puisqu'il est trivialement vérifié pour ''n'' = 1.
En faisant 
:<math>P(X) = X^2 - a, \quad m_1 = p^n \quad \hbox{et}\quad m_2 = p</math> 
dans le lemme ci-dessus, on obtient d'abord
:<math>P(x') = x'^2 - a \equiv 0 \mod p^n</math>, 
qui a bien une solution <math>x'</math> par l'hypothèse de récurrence, d'ailleurs première avec ''p'' puisque <math>a</math> l'est.
Puis
:<math>Q(x'') = p^Nx''^2 + 2x' x'' + {x'^2-a\over p^{N}} \equiv 0 \mod p</math>,
qui n'est autre qu'une [[Congruence linéaire|é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 {{mvar|a}} congru à 1 modulo 8 est résidu quadratique modulo ''2{{exp|n}}'']], <math>n \in \mathbb N</math>  (réciproque immédiate pour ''n'' > 2 et {{mvar|a}} 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|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.

{{Démonstration/fin}}

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 [[Rivest Shamir Adleman|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>{{Article|prénom1=Manindra|nom1=Agrawal|prénom2=Somenath|nom2=Biswas|titre=Primality and Identity Testing via Chinese Remaindering|périodique=Proceedings of the 40th Annual Symposium on Foundations of Computer Science|série=FOCS '99|éditeur=IEEE Computer Society|date=1999|isbn=9780769504094|lire en ligne=http://dl.acm.org/citation.cfm?id=795665.796517|consulté le=2019-07-09|pages=202–}}</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.

== Suite ==
De façon triviale, voici la suite des 1000 premières itérations répondant à l'énoncé d'origine dit des « restes chinois » (différence de 105 entre deux termes):

23, 128, 233, 338, 443, 548, 653, 758, 863, 968

La suite relative aux pirates, pour les 5000 premières itérations, donne (différence de 1122 entre deux termes) :

785, 1907, 3029, 4151.

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
*[[Théorème de Bachet-Bézout]]
*[[Système couvrant]]
=== Bibliographie ===
*{{Ouvrage|
titre=Cours d'algèbre. Primalité. Divisibilité. Codes.|
auteurs=[[Michel Demazure]]|
éditeur=Cassini|
collection=Nouvelle bibliothèque mathématique|
numéro dans collection=1|
année=1997|
édition=Première édition|
isbn=978-2842250003}}

* {{Ouvrage|auteur1=[[Ronald Graham]]|auteur2=[[Donald Knuth]]|auteur3=[[Oren Patashnik]]|traducteur=Alain Denise|titre=[[Mathématiques concrètes]]|sous-titre=Fondations pour l'informatique|lieu=Paris|éditeur=[[Vuibert]]|année=2003|numéro d'édition=2|pages totales=xiv+688|isbn=978-2-7117-4824-2}}

=== Liens externes ===
* {{en}} [http://www.cut-the-knot.org/blue/chinese.shtml {{Langue|en|Chinese Remainder Theorem}}] sur [[cut-the-knot]]

{{Portail|mathématiques}}

{{DEFAULTSORT:Restes chinois}}
[[Catégorie:Arithmétique modulaire]]
[[Catégorie:Théorème de la théorie des nombres]]