Théorème des restes chinois - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

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, établi initialement pour Z/nZ, se généralise en théorie des anneaux. Ce théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) est utilisé en théorie des nombres (Traditionnellement, la théorie des nombres est une branche des mathématiques qui s'occupe...).

Fragments d'histoire

La forme originale du théorème, 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 :

Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?

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 :

Dans combien de jours la pleine lune (La pleine Lune est la phase lunaire durant laquelle la Lune apparaît la plus brillante depuis...) tombera-t-elle au solstice (Le solstice est un événement astronomique qui se produit lorsque la position apparente du...) d'hiver ?

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 :

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 ?

La résolution proposée par Sun Zi pour le problème des soldats 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.

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 :

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 ?

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.

Résultat pour les anneaux

Dans les anneaux \mathbb Z/n\mathbb Z

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 des ni, l'application

 \begin{matrix} \phi:&\mathbb{Z}/n\mathbb{Z} &\longrightarrow& \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}\\      &\alpha                 &\longmapsto& (\alpha[n_1],\dots,\alpha[n_k]) \end{matrix}

est un isomorphisme d'anneau.

Pour le montrer, on remarque d'abord que les deux ensembles \mathbb{Z}/n\mathbb{Z} et \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z} ont le même nombre d'éléments. Comme \phi\, est un morphisme d'anneau, 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 α = 0[ni] pour i=1, \dots, k, c’est-à-dire si α est un multiple de chaque ni, alors α = 0[n], c’est-à-dire α est un multiple du produit n_1\dots n_k. Ceci résulte de l'hypothèse que les ni sont premiers entre eux deux à deux.

Dans le cas où les ni ne sont pas premiers entre eux, n est leur ppcm et le morphisme ci-dessus n'est qu'injectif. Il existe une solution au problème initial si et seulement si les données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) sont dans l'image, c'est-à-dire que le pgcd de ni et nj divise αi − αj pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) couple i,j.

Dans un anneau principal (Les anneaux principaux forment un type d'anneaux important dans la théorie mathématique...)

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

f : R/uR \rightarrow R/u_1R \times \cdots \times R/u_k R

tel que

x \;\mathrm{mod}\,uR \rightarrow (x \;\mathrm{mod}\,u_1R) \times \cdots \times (x \;\mathrm{mod}\,u_kR)

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

rui + su / ui = 1

Fixons ei = s u/ui. On a :

e_i \equiv 1 \pmod{u_i} \quad\mathrm{et}\quad e_i \equiv 0 \pmod{u_j}

pour ji.

Alors l'inverse est la transformation

g : R/u_1R \times \cdots \times R/u_kR \rightarrow R/uR

telle que

(a_1 \;\mathrm{mod}\,u_1R) \times \cdots \times (a_k \;\mathrm{mod}u_kR) \rightarrow \sum_{i=1..k} a_i e_i \pmod{uR}

Résultat pour les anneaux généraux

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 ij), 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 R/I_1 \times \cdots \times R/I_k qui à x \;\mathrm{mod}\,I associe (x \;\mathrm{mod}\,I_1) \times \cdots \times (x \;\mathrm{mod} I_k).

Page générée en 0.104 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique