Discussion:Théorème des restes chinois

3ieD ???

Peut-être bien que le vandale se rachète à voir l'histo :

• 19 janvier 2006 à 15:57 129.102.254.253 (→Système de congruences d'entiers)

129.102.254.253 20 janvier 2006 à 18:41 (CET)

Pseudocode

Lors de cette fusion, j'ai mis en commentaires les remarques sur le pseudo-code qui me semble mélanger raisonnement mathématique et algorithmique. Il me semble que, si ce pseudo code se révèle utile, il doit être mis dans une chapitre à part. Si d'ici quelques temps, personne ne réagit, je supprimerai simplement ces pseudocodes. HB 4 août 2006 à 17:53 (CEST)

Le problème "le plus célèbre"

Quelle est son origine ? Peps 4 août 2006 à 18:14 (CEST)

Ca c'est une colle ! l'exemple des pirates et du butin est l'exemple le plus souvent cité pour illustrer le théorème des restes chinois je n'en connais pas l'origine. HB 4 août 2006 à 18:22 (CEST)

Je croyais que l'exemple le plus célèbre était celui de Sun Zi, non ? Mais en tout cas, ce n'est pas Sun Zi qui a découvert le résultat. Evidemment, l'origine des théorèmes des restes chinois est plus ancienne. Je parie qu'Euclide connaissait le résultat, mais je ne peux pas le jurer. La dynastie chinoise l'utilisait pour aligner les calandriers solaires et lunaires. J'ai aussi lu (souvenir) que les incas avaient indépendemment découvert ce résultat artihmétique (on ne sait pas trop quand) et pout les mêmes raisons (calculs sur les calandriers).

A mon avis, le résultat est tellement simple qu'il a été indépendemment établi par plusieurs personnes à plusieurs époques et dans plusieurs lieux. Ektoplastor

785 mon cher Watson. Pourquoi a-t-on supprimé ce 785?Jean ^{[de Parthenay]} 14 mars 2018 à 14:20 (CET)

Démonstration de la forme générale

Il me semble que l'article ne contient pas de démonstration de la forme générale du théorème chinois (où les modules des congruences ne sont pas forcément premiers entre eux). La preuve par récurrence sur le nombre de congruences ne me semble pas difficile, mais elle repose sur la distributivité du pgcd par rapport au ppcm.

Voici une rédaction de cette démonstration :

a) Soient a, b et c des entiers rationnels. Pour qu'il exite un entier rationnel x tel que

$ax\equiv b{\pmod {c}}$

il faut et il suffit que b soit divisible par le pgcd de a et c.

Démonstration. Sil existe un entier rationnel x tel que

$ax\equiv b{\pmod {c}},$

alors b = ax + cr pour un certain entier rationnel r, donc b est clairement divisible par le pgcd de a et c. Réciproquement, supposons que b soit divisible par le pgcd de a et c. Soit d ce pgcd. Il existe donc un entier rationnel s tel que b = sd. D'autre part, d'après le théorème de Bézout, il existe des entiers rationnels t et u tels que ta + uc = d. En multiplianr par s, nous trouvons sta + suc = b, d'où

$sta\equiv b{\pmod {c}}$

d'où

$ax\equiv b{\pmod {c}}$

avec x =st.

b) (Théorème chinois) Soient m₁, ... , m_n des entiers naturels et a₁, ... , a_n des entiers rationnels. On suppose que pour tous indices i, j distincts,

$\qquad a_{i}\equiv a_{j}{\pmod {\mathrm {pgcd} (m_{i},m_{j})}}.$

Il existe un entier rationnel a tel que, pour tout i (1 ≤ i ≤ n),

$\qquad a\equiv a_{i}{\pmod {m_{i}}}.$

Prouvons-le d'abord dans le cas particulier n = 2. Il s'agit de prouver que si m₁ et m₂ sont des nombres naturels, si a₁ et a₂ sont des entiers rationnels tels que

$(1)\qquad a_{1}\equiv a_{2}{\pmod {\mathrm {pgcd} (m_{1},m_{2})}},$

il existe un entier rationnel a tel que

$a\equiv a_{1}{\pmod {m_{1}}}$

et

$a\equiv a_{2}{\pmod {m_{2}}}.$

D'après l'hypothèse (1), a₁ - a₂ est divisible par pgcd(m₁, m₂), donc, d'après le point a), il existe un entier rationnel x tel que

$a_{1}-a_{2}\equiv xm_{1}{\pmod {m_{2}}},$

autrement dit, il existe des entiers rationnels x et y tels que

$\ a_{1}-a_{2}=xm_{1}+ym_{2}.$

On a alors a₁ - x m₁ = a₂ + y m₂, donc la valeur commune de a₁ - x m₁ et a₂ + y m₂ convient pour a.
Nous avons donc démontré l'énoncé dans le cas particulier où n = 2. Passons au cas général. L'énoncé est banalement vrai si n = 0. Soit n un nombre naturel ≥ 1. Supposons l'énoncé vrai pour n - 1 (hypothèse de récurrence) et prouvons-le pour n. Par hypothèse de récurrence, nous pouvons choisir un entier rationnel b tel que

$b\equiv a_{1}{\pmod {m_{1}}}$

...

$b\equiv a_{n-1}{\pmod {m_{n-1}}}.$

Pour démontrer l'énoncé, il suffit clairement de prouver qu'il existe un entier rationnel a tel que

$a\equiv b{\pmod {\mathrm {ppcm} (m_{1},\ldots m_{n-1})}}$

et

$a\equiv a_{n}{\pmod {m_{n}}}.$

Puisque nous avons démontré l'énoncé dans le cas particulier où n = 2, il suffit de prouver que

$a_{n}\equiv b{\pmod {\mathrm {pgcd} (m_{n},\mathrm {ppcm} (m_{1},\ldots m_{n-1}))}}.$

Puisque le pgcd est distributif par rapport au ppcm, nous avons

$\mathrm {pgcd} (m_{n},\mathrm {ppcm} (m_{1},\ldots m_{n-1}))=\mathrm {ppcm} (\mathrm {pgcd} (m_{1},m_{n}),\ldots ,\mathrm {pgcd} (m_{n-1},m_{n})),$

donc il s'agit de prouver que

$a_{n}\equiv b{\pmod {\mathrm {ppcm} (\mathrm {pgcd} (m_{1},m_{n}),\ldots ,\mathrm {pgcd} (m_{n-1},m_{n}))}}.$

Ceci revient à prouver que

$a_{n}\equiv b{\pmod {\mathrm {pgcd} (m_{i},m_{n})}}$

pour chaque i (1 ≤ i ≤ n-1). Cette congruence résulte du fait que a_n et b sont tous deux congrus à a_i modulo pgcd(m_i, m_n). (Pour a_n, c'est vrai d'après les hypothèses de l'énoncé; pour b, cela résulte clairement du choix de b.)

Cette démonstration me semble tout à fait différente de celle qui est donnée dans le cas particulier où les modules des congruences sont premiers entre eux. Trouve-t-on qu'il serait utile de mettre la démonstration générale dans l'article ?
Marvoir (d) 21 mai 2009 à 12:11 (CEST)

Il y a 2 articles "plus généraux" (potentiellement) : Théorème de congruence linéaire et Méthode des substitutions successives. Actuellement seul le 2ème est cité ici. Il me semble que le mieux serait de fusionner le 2ème dans le 1er, y ajouter ta démo, citer ici le 1er au lieu du 2ème, et sortir ce 1er de son orphelinat. Anne 4 février 2011 à 01:01

D'accord. Je suggère que tu fasses à ton idée, car je n'ai jamais étudié de près la question des systèmes de congruences linéaires. Marvoir (d) 6 février 2011 à 13:11 (CET)

J'ai fini par (plutôt que fusionner) rediriger Méthode des substitutions successives sur Théorème de congruence linéaire, sans perte d'information. Plutôt qu'enrichir ce dernier (traduit d'un ancien article en anglais, et au titre difficile à sourcer), j'envisage de le rediriger vers un nouvel article Congruence linéaire. Je me sers de cette section de pdd comme bloc-notes avant de le créer (j'ai diverses idées d'autres méthodes mais je cherche à les sourcer).

• On peut remplacer la démonstration de (a) ci-dessus par : résoudre ax ≡ b mod c revient à résoudre ax + cy = b.
• Dans l'article de MacTutor sur Qin Jiushao on lit : « His next move, therefore, is to make various passes through the mk making replacements in such a way that eventually the new moduli are pairwise coprime but the solution to the original problem remains unchanged by the replacements. » Je ne sais pas quels étaient ses habiles « various passes through the mk ».
• Une variante (peut-être plus facile à présenter mais algorithmiquement plus coûteuse) est dans Gareth A. Jones et Josephine M. Jones, Elementary Number Theory, Springer Science+Business Media, 1998, p. 60-61.

Anne 14/9/14 16h10

Comme je te l'avais déjà dit, je te laisse les mains entièrement libres. À part la démonstration que j'ai écrite ci-dessus, je ne connais pas la question, en particulier je ne sais rien de l'aspect algorithmique. Marvoir (discuter) 14 septembre 2014 à 16:37 (CEST)

Truc louche

Le passage "sur les anneaux généraux", qui ne suppose pas la commutativité, me semble confus et probablement tout faux - ça ne doit guère être sauvable qu'en ajoutant de la commutativité. Comme il n'y a pas de source, c'est difficile d'être sûr que c'est la seule réparation possible. Si quelqu'un a un deuxième avis... Touriste (d) 2 février 2011 à 20:45 (CET)

en:Chinese remainder theorem#Non-commutative case: a counter-example : vrai pour I=l'intersection, mais cette intersection n'est pas égale "au" produit, seulement à la somme des produits. Voir aussi la pdd de :en, qui mentionne Hungerford. Anne Bauval (d) 4 février 2011 à 01:28 (CET)

Fait, grâce finalement à Bourbaki. J'ai des doutes sur l'expression plus simple de l'intersection (comme une somme de k produits au lieu de k!) proposée par un contributeur dans le diff ci-dessus de la pdd de :en, donc je ne l'ai pas ajoutée. Anne Bauval (d) 6 février 2011 à 02:58 (CET)

Exemple ?

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.

???

Exemple

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=105$

Algorithme d'Euclide étendu

• $n_{1}=3$ et ${\hat {n}}_{1}=35\times (-1)$ , or ${\hat {n}}_{1}\equiv 1{\pmod {3}}$ donc $e_{1}=-35$
• $n_{2}=5$ et ${\hat {n}}_{2}=21\times (1)$ , or ${\hat {n}}_{2}\equiv 1{\pmod {5}}$ donc $e_{2}=21$
• $n_{3}=7$ et ${\hat {n}}_{3}=15\times (1)$ , or ${\hat {n}}_{3}\equiv 1{\pmod {7}}$ donc $e_{3}=15$

une solution pour x est alors $x=2\times (-35)+3\times 21+2\times 15=23$

et les solutions sont tous les entiers congrus à 23 modulo 105.

--79.196.7.248 (d) 3 février 2011 à 17:18 (CET)

Certes, il a plusieurs solutions possibles pour e1, e2 et e3. En choisissant la première version, on montre comment la théorie sur les congruences permet de retrouver la solution proposée par SunZi. Cette deuxième version permet d'aboutir à un nombre plus petit mais fait perdre de l'unité et de la cohérence à l'ensemble. C'est la raison pour laquelle je préfèrerais revenir aux valeurs de e1, e2, e3 précédentes qui ont le bon goût d'être positives, de coller à la solution chinoise et d'expliquer pourquoi on doit retirer plusieurs fois 105. HB (d) 3 février 2011 à 23:01 (CET)

Tu m'as si bien convaincue que c'était un plaisir de m'autoreverter. Après réflexion j'irais même plus loin : ai-je bien fait d'ajouter ensuite le lien Algorithme d'Euclide étendu proposé ci-dessus par 79.196.7.248 ? même si oui, l'ai-je placé au mieux ? et surtout : ne serait-il pas mieux de lier vers Inverse modulaire, et d'ajouter là-bas qqchse sur l'algorithme "naïf" d'inversion de la classe de a mod b (quand a et b premiers entre eux) qui consiste à ajouter a autant (>0) de fois qu'il faut pour que le résidu devienne 1 ? Anne Bauval (d) 6 février 2011 à 03:19 (CET)

Zachariou

A la question qui est Zachariou ? Je répondrais bien : probablement Andréas Zachariou, qui a publié plusieurs articles sur les nombres premiers. Ce qui me gène davantage est de faire figurer sur WP le résultat d'une conversation privée qui n'était probablement pas à visée scientifique : Ribenboim écrit « However, according to A. Zachariou (private communication) it was known even before them by the Greeks ». HB (d) 27 avril 2013 à 18:23 (CEST)

Ah, merci. Bon, on peut garder, mais à mon avis, seulement en note.--Dfeldmann (d) 28 avril 2013 à 05:22 (CEST)

L'indication I^er siècle pour « Sun-Tsu » que donne

(en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. 2, p. 57

est apparemment périmée mais il signale un autre fait intéressant p. 58 : le même problème résolu (x ≡ 2 mod 3, 3 mod 5, 5 mod 7, solution x = 23) apparaissait déjà dans

l'Introduction à l'arithmétique (en) de Nicomaque de Gérase vers l'année 100 (livre 2, éd. de Hoche, 1866, supplément, prob. 5).

Hélas l'éd. de Hoche est en grec, et dans la traduc en anglais je ne trouve pas cet exemple.

(en) James Joseph Tattersall, Elementary Number Theory in Nine Chapters, 1999 (lire en ligne), p. 173,

pour qui le livre de Sun-Tzu date de la fin du III^e siècle, mentionne aussi que Nicomaque donnait déjà cet exemple, et insiste : « quite remarkably, as an indication of the transmission of knowledge in the ancient world ». Anne 18 septembre 2014 à 02:21

La question de l'origine de ce problème est bien exposée à mon avis sur le site de l'ENS : http://culturemath.ens.fr/materiaux/irem-toulouse11/questions-sur-les-origines.html. On y lit que le problème apparait en annexe de l'oeuvre de Nicomaque de Gerase, chez un mathématicien byzantin du XIVe siècle Isaac Argyros, soit après les chinois et les arabes. Ricardus Hoche semble faire une recension de tous les écrits se rapportant à l'introduction à l'arithmétique. Normalement, il indique le système de transmission. Je lis mal le latin mais j'ai l'impression que la dernière section qui contiendrait le problème (Problèmes arithmétiques) est donnée en supplément (accedunt codicis cizensis problemata arithmetica). HB (discuter) 18 septembre 2014 à 14:59 (CEST)

théorème et démonstration

Il semble que Théorème des restes chinois#Th.C3.A9or.C3.A8me soit l'énoncé du théorème et sa démonstration. par contre j'ai l'impression que l'unicité de x modulo n n'est pas démontrée. Xavier Combelle (discuter) 18 août 2017 à 00:28 (CEST)

Inversé historique

"On retrouve ce problème presque à l'identique en 1202 dans le Liber Abbaci de Fibonacci3 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."

Si on veut être honnête, il faut mettre dans l'ordre chronologique :

• Le problème avait été étudié par Ibn al-Haytham (Alhazen) (XI-XIIe siècle)

• puis Fibonacci "a pu" en lire les oeuvres (les a-t-il lues ? Ou avait-il seulement la possibilité chronologique de s'en inspirer ?)

• puis Fibonacci en a fait un livre (Liber Abbaci), incluant le "problème des lapins"

J'avais déjà rétabli dans l'ordre chronologique, mais ma modif a été annulée. Les Arabes font-ils peur au point qu'il faille les mettre en fin de paragraphe ? Faut-il mettre Fibonacci en super-star au point d'éclipser tout Chinois ou Allemand ou Perse qui pourrait lui faire de l'ombre ? Le texte initial est-il "gravé dans le marbre" et sacré au point que ce serait un sacrilège de ma part que d'en changer une virgule ? Je ne sais pas pourquoi ma modif a été annulée... Magnon86 (discuter) 15 avril 2018 à 08:31 (CEST)magnon86

Tel que c'est écrit, la phrase "dont Fibonacci a pu lire les œuvres" a un sens quand Fibonacci a déjà été cité. Il aurait fallu reprendre la rédaction. Sinon je ne vois pas en quoi l'ordre chronologique serait plus "honnête", ni pourquoi Ibn al-Haytham est plus ou moins visible suivant la formulation (je ne parle pas des interprétations complotistes qui suivent). Il peut y avoir des raisons d'inverser l'ordre (par exemple on a découvert plus tard les travaux de Ibn al-Haytham). Là c'est peut-être tout simplement un ajout ultérieur à l'économie d'un second rédacteur. Le mieux pour modifier ce paragraphe serait d'avoir une source (à propos d'Ibn al-Haytham), voire une à propos de son influence éventuelle sur Fibonacci. Proz (discuter) 17 avril 2018 à 20:25 (CEST)

Nom anglais

Salut, ne voyant pas ce que le nom anglais du théorème des restes chinois aurait de pertinent (il ne répond même pas à la question que tout le monde se pose : c’est le théorème ou les restes qui sont chinois ?), je le supprime. — Maëlan 2 octobre 2019 à 15:06 (CEST)

Sans trop m'avancer, je pense que le terme anglais était là pour justifier les initiales CRT employées en français pour faire référence à ce théorème, comme dans la méthode RSA CRT.

concernant le nom auquel se rapporte l'adjectif chinois, je n'en ai aucune idée. La syntaxe penche pour le nom le plus proche restes, mais je pense que, comme toute forme figée, il faut la prendre comme elle est sans trop chercher à la décortiquer (sauf si les sources le font).

HB (discuter) 2 octobre 2019 à 15:37 (CEST)