Théorème des restes chinois

Le théorème des restes chinois est un résultat d'arithmétique modulaire traitant de résolution de dispositifs de congruences.



Catégories :

Arithmétique modulaire - Algèbre - Théorème de mathématiques

Page(s) en rapport avec ce sujet :

  • Supposons que nous ayons deux solutions x1 et x2 du dispositif : on a alors x1..... Le Théorème des restes chinois est utilisé pour simplifier les calculs... (source : ybonnet.free)

Le théorème des restes chinois est un résultat d'arithmétique modulaire traitant de résolution de dispositifs de congruences. Ce résultat, établi originellement pour Z/nZ, 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, contenue dans un ouvrage du mathématicien chinois Qin Jiushao publié en 1247, est un résultat concernant les dispositifs de congruences (voir arithmétique modulaire). Mais on trouve trace d'un problème analogue dans le livre de Sun 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 et qu'ils aient été amenés particulièrement 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 tandis 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 ?

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, particulièrement souvent 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 aussi, et de donner le reste au cuisinier chinois. Ce dernier 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 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 quand ij). Alors pour tous entiers a1, ..., ak, il existe un entier x, unique modulo 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 selon le théorème de Bachet-Bézout, on peut trouver des entiers u_i\, et v_i\, tels que u_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 dispositif de congruences est donc

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

D'une façon plus générale, l'ensemble des solutions x de ce dispositif 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

une solution pour x est alors x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233

et les solutions sont l'ensemble des entiers congrus à 233 modulo 105, c'est-à-dire à 23 modulo 105.

Généralisation à des nombres non premiers entre eux

Parfois, les dispositifs 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 uniquement si a_i \equiv a_j \pmod {Pgcd(n_i,n_j)}\, pour tous i et j. L'ensemble des solutions x sont congrues modulo le PPCM des ni.

Exemple : résoudre le dispositif

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

équivaut à résoudre le dispositif

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

équivaut au dispositif

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

Une solution est par conséquent x = 3 \times 9 + 2 \times 4 = 35 ou tout autre nombre congru à 11 modulo 12

La méthode des substitutions successives peut fréquemment apporter les solutions des dispositifs de congruences, même quand les modules ne sont pas premiers entre eux deux à deux.

Interprétation mécanique

La résolution du dispositif 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 dentée comportant a dents s'engrène dans une tringle horizontale. Combien de dents doivent passer pour que sa r-ième dent vienne en coïncidence avec la s-ième dent d'une autre roue dentée comportant elle b dents ?

Le PPCM des deux nombres a et b est ce qui sert à comprendre le comportement périodique de ce dispositif : c'est le nombre de dents séparant deux contacts de même congruence. On peut par conséquent 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. GeoplanPpcm.png

On peut comprendre simplement pourquoi le calcul sur des roues dentées fait intervenir de l'arithmétique modulaire, en remarquant que la totalité des dents d'une roue en comptant n peut être paramétré par la totalité des racines nèmes de l'unité, qui a une structure de groupe naturellement isomorphe à celle de Z/nZ.

Résultat pour les anneaux

Dans les anneaux \mathbb Z/n\mathbb Z

Article détaillé : Anneau Z/nZ.

Le théorème chinois a aussi 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 en premier lieu 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 par conséquent 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 d'origine si et uniquement si les données sont dans l'image, c'est-à-dire que le pgcd de ni et nj divise αi − αj pour tout couple i, j.

Dans un anneau principal

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si u1, ..., uk sont les éléments de R qui sont premiers entre eux deux à deux, et u sert à désigner 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 peut être construit comme ceci. Pour chaque i, les éléments ui et u/ui sont premiers entre eux, et donc, 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 (à 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 quand 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 habituel 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 différents 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. D'autre part, modulo Ui, X ≡ xi, de sorte que Ei ≡ 1 modulo Ui.

Dire qu'un polynôme 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é surtout dans l'algorithme RSA en cryptographie.

Il sert à 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.

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu