Théorème des restes chinois
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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.

Fragments d'histoire

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 assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à...), contenue dans un livre du mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité principale. Ce terme recouvre une large palette de...) 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 théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On...) modulaire). Mais on trouve trace (TRACE est un télescope spatial de la NASA conçu pour étudier la connexion entre le champ magnétique à petite échelle du Soleil et la...) d'un problème analogue dans le livre de Sun (Sun Microsystems (NASDAQ : SUNW) est un constructeur d'ordinateurs et un éditeur de logiciels américain.) 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é inventés par les hommes pour mesurer, diviser et organiser le temps sur...) 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 la Terre, de par le fait que nous voyons, lors de cette phase, presque toute la surface lunaire éclairée par le...) tombera-t-elle au solstice (Le solstice est un événement astronomique qui se produit lorsque la position apparente du Soleil vu de la Terre atteint son extrême méridional ou septentrional.) 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 système solaire avec un diamètre de 3 474 km. La...), 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 création des États, un groupe d’hommes sédentarisés libres (pouvant avoir des esclaves),...) 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 a rendu (Le rendu est un processus informatique calculant l'image 2D (équivalent d'une photographie) d'une scène créée dans un logiciel de modélisation 3D comportant à la fois des objets et des sources de...) ce type de problème plus facile à résoudre.

Système de congruences d'entiers

Théorème

Soient n1, ..., nk des entiers deux à deux premiers entre eux (ce qui veut dire pgcd (ni , nj) = 1 lorsque ij). 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 être associé à d'autres formes de congruence En informatique, le...) n=\prod_{i=1}^k n_i et tel que

\begin{matrix} x \equiv a_1\pmod{n_1}\\  \ldots \\  x \equiv a_k\pmod{n_k}\\ \end{matrix}

Une solution x peut être trouvée comme suit:

Pour chaque i, les entiers n_i\, et \hat n_i = \frac{n}{n_i} sont premiers entre eux, et en utilisant l'identité de Bézout, on peut trouver des entiers u_i\, et v_i\, tels queu_in_i + v_i\hat n_i= 1. Si on pose e_i =  v_i\hat n_i, alors nous avons

e_i \equiv 1 \pmod{n_i} \,

et

e_i \equiv 0 \pmod{n_j}\, pour ji.

Une solution de ce système de congruences est par conséquent

x = \sum_{i=1}^k a_i e_i\

Plus généralement, toutes les solutions x de ce système sont congrues modulo le produit n

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

  • n1 = 3 et \hat n_1 = 35 , or 2\hat n_1\equiv 1 \pmod{3} donc e1 = 70
  • n2 = 5 et \hat n_2 = 21 , or \hat n_2\equiv 1 \pmod{5} donc e2 = 21
  • n3 = 7 et \hat n_3= 15 , or \hat n_3\equiv 1 \pmod{7} donc e3 = 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.

Généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent...) à des nombres non premiers entre eux

Quelquefois, les systèmes de congruences peuvent être résolus même si les n_i\, ne sont pas premiers entre eux deux à deux. Le critère précis est le suivant : une solution x existe si et seulement si a_i \equiv a_j \pmod {Pgcd(n_i,n_j)}\, pour tous i et j. Toutes les solutions x sont congrues modulo le PPCM des ni .

Exemple : résoudre le système

x \equiv 3 \pmod{4} \,
x \equiv 5\pmod{6} \,

équivaut à résoudre le système

x \equiv 3 \pmod{4} \,
x \equiv 1 \pmod{2} \,
x \equiv 1 \pmod{2} \,
x \equiv 2\pmod{3} \,

équivaut au système

x \equiv 3 \pmod{4} \,
x \equiv 2\pmod{3}\,
  • n1 = 4 et \hat n_1 = 3 , or 3\hat n_1\equiv 1 \pmod{4} donc e1 = 9
  • n2 = 3 et \hat n_2 = 4 , or \hat n_2\equiv 1 \pmod{3} donc e2 = 4

Une solution est donc x = 3 \times 9 + 2 \times 4 = 35 ou tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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.

Interprétation mécanique (Dans le langage courant, la mécanique est le domaine des machines, moteurs, véhicules, organes (engrenages, poulies, courroies, vilebrequins, arbres de transmission,...)

La résolution du système suivant :

\left\{\begin{array}{l}     x\equiv r \pmod a \\   x\equiv s \pmod b \end{array}\right.

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 son centre.) 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 Brisson (1723-1806) en 1760.) pour que sa r-ième dent (Une dent est un organe enveloppé d'os, dur, blanchâtre, généralement composé d'une couronne libre et d'une ou plusieurs racines implantées dans la cavité buccale, plus...) 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 passant par son centre.) 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. Image:GeoplanPpcm.png

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 d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) 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 \mathbb{Z}/n\mathbb{Z}.

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

\begin{matrix} \phi:&\mathbb{Z}/n\mathbb{Z} &\mapsto& \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}\\      &\alpha                 &\mapsto& (\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 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 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 un anneau principal

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 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...) 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 composition interne · notée multiplicativement, est un élément y tel que x·y = y·x = 1, si 1...) 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. Les idéaux généralisent de façon féconde l'étude de la divisibilité pour les entiers. Il...) (à 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).

Exemple des polynômes

Un cas fréquent illustrant le paragraphe précédent est donné par l'anneau \mathbb K[X] des polynômes. Si x0, x1, ..., xn sont n+1 éléments de \mathbb K 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 : 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)}.

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 (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent...) 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 P = \sum_{i=0}^n y_i E_i , ce qu'on peut vérifier par un calcul direct.

Utilisations

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 (assurant confidentialité, authenticité et intégrité) en s'aidant...).

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 réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou les volumes. En...) ou la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) peuvent se faire en parallèle en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) constant (pas de propagation de retenue). Par contre, la comparaison ou la division ne sont pas triviales.

Page générée en 1.179 seconde(s) - site hébergé chez Amen
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