Théorème_des_restes_chinois

Un article de Wikipedia.y-project.com.

Le théorème des restes chinois est un nom en relation avec plusieurs résultats de l'algèbre abstraite et de la théorie des nombres.

Sommaire 1 Système de congruences d'entiers 2 Résultat pour les anneaux principaux 3 Exemple des polynômes 4 Résultat pour les anneaux généraux 5 Liens externes

[] Système de congruences d'entiers

La forme originale du théorème, contenue dans un livre du mathématicien chinois Qin Jiushao publié en 1247, est un résultat concernant les systèmes de congruences (voir arithmétique modulaire). Supposons que n₁, ..., n_k soient des nombres entiers positifs qui sont premiers entre eux deux à deux. (ce qui veut dire pgcd (n_i, n_j) = 1 lorsque i ? j). Alors, pour n'importe quels entiers donnés a₁, ..., a_k, il existe un entier x qui résout un système de congruences

<math>x \equiv a_i \pmod \quad\mathrm\; i = 1, \cdots, k</math>

« Sous-titre » en pseudocode :

x_solves_it=true;
for(i= 1; i <= k; i++)
   if(x % n[i] != a[i] % n[i])
      x_solves_it=false;

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

Un solution x peut être trouvée comme suit. Pour chaque i, les entiers n_i et n/n_i sont premiers entre eux, et en utilisant l'algorithme d'Euclide étendu, nous pouvons trouver les entiers r et s tels que r n_i + s n/n_i = 1. Si nous fixons e_i = s n/n_i, alors nous avons

<math>e_i \equiv 1 \pmod \quad\mathrm\quad

e_i \equiv 0 \pmod</math>

pour j ? i.

for (i= 1; i <= k; i++)
  {r, s}= ExtendedEuclid( n[i], n / n[i] );
  e[i]= s * n / n[i];
  for(j= 1; j <= k; j++)
    if (j != i)
      assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

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

<math> x = \sum_ a_i e_i\ </math>

for(i= 1; i <= k; i++)
  x += a[i] * e[i];

Par exemple, considérons le problème suivant : trouver un entier x tel que

<math>x \equiv 2 \pmod </math>

<math>x \equiv 3 \pmod </math>

<math>x \equiv 2 \pmod </math>

 x % 3 == 2 % 3 &&
 x % 4 == 3 % 4 &&
 x % 5 == 2 % 5

En utilisant l'algorithme d'Euclide étendu pour 3 et 4×5 = 20, nous trouvons (-13) × 3 + 2 × 20 = 1, c.a.d. e₁ = 40 (e[1] == 40). En utilisant l'algorithme d'Euclide pour 4 et 3 × 5 = 15, nous avons (-11) × 4 + 3 × 15 = 1. Ainsi, e₂ = 45 (e[2] == 45). Finalement, en utilisant l'algorithme d'Euclide pour 5 et 3×4 = 12, nous avons 5 × 5 + (-2) × 12 = 1, ce qui veut dire e₃ = -24 (e[3] == -24). Une solution x est par conséquent 2 × 40 + 3 × 45 + 2 × (-24) = 167. Toutes les autres solutions sont congrues à 167 modulo 60, ce qui signifie qu'elles sont toutes congrues à 47 modulo 60.

Quelquefois, les systèmes de congruences peuvent être résolus même si les n_i de (n[i]'s) 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 ? a_j (mod pgcd(n_i, n_j)) (a[i] == a[j] % gcd(n[i], n[j]) pour tous les i et j. Toutes les solutions x sont congrues modulo le PPCM des n_i (n[i]).

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.

[] Résultat pour les anneaux principaux

Pour un anneau principal R, le théorème des restes chinois prend la forme suivante : Si u₁, ..., u_k sont les éléments de R qui sont premiers entre eux deux à deux, et u désigne le produit u₁...u_k, alors l'anneau R/uR et l'anneau produit R/u₁R x ... x R/u_kR sont isomorphes par l'isomorphisme

<math>f : R/uR \rightarrow R/u_1R \times \cdots \times

R/u_k R </math>

tel que

<math>x \;\mathrm\,uR \rightarrow (x \;\mathrm\,u_1R) \times \cdots \times

(x \;\mathrm\,u_kR) </math>

L'isomorphisme inverse peut être construit comme ceci. Pour chaque i, les éléments u_i et u/u_i sont premiers entre eux, et par conséquent, il existe des éléments r et s dans R avec

<math>r u_i + s u/u_i = 1 </math>

Fixons e_i = s u/u_i. On a :

<math>e_i \equiv 1 \pmod \quad\mathrm\quad

e_i \equiv 0 \pmod</math>

pour j ? i.

Alors l'inverse est la transformation

<math>g : R/u_1R \times \cdots \times R/u_kR

\rightarrow R/uR </math>

telle que

<math>(a_1 \;\mathrm\,u_1R) \times \cdots \times (a_k \;\mathrmu_kR) \rightarrow

\sum_ a_i e_i \pmod </math>

[] Exemple des polynômes

Un cas fréquent illustrant le paragraphe précédent est donné par l'anneau <math>\mathbb K[X]</math> des polynômes. Si x₀, x₁, ..., x_n sont n+1 éléments de <math>\mathbb K</math> distincts deux à deux, alors on peut prendre U_i = X - x_i . Les polynômes U_i sont premiers entre eux deux à deux, et le théorème des restes chinois s'applique. On prend pour E_i les polynômes interpolateurs de Lagrange, définis par : <math>E_i = )(X-x_)...(X-x_n) \over(x_i-x_0)(x_i-x_1)...(x_i-x_)(x_i-x_)...(x_i-x_n)}</math>.

Pour j différent de i, E_i est divisible par U_j , de sorte que E_i ? 0 modulo U_j . Par ailleurs, modulo U_i , X ? x_i , de sorte que E_i ? 1 modulo U_i .

Dire qu'un polynôme P est tel que P(x_i) = y_i pour tout i, est équivalent à dire que P ? y_i modulo U_i . Un tel polynôme P est donné par <math>P = \sum_^n y_i E_i</math> , ce qu'on peut vérifier par un calcul direct.

[] 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 I₁, ..., I_k des idéaux de R qui sont deux à deux premiers entre eux (ce qui signife que I_i + I_j = R lorsque i ? j), alors l'anneau produit I de ces idéaux est égal à leur intersection, et l'anneau quotient R/I est isomorphe à l'anneau produit R/I₁ x R/I₂ x ... x R/I_k via l'isomorphisme de <math>R/I</math> dans <math>R/I_1 \times \cdots \times R/I_k </math> qui à <math>x \;\mathrm\,I</math> associe <math>(x \;\mathrm\,I_1) \times \cdots \times (x \;\mathrm I_k)</math>.

[] Liens externes

• Théorème des restes chinois

 
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Théorème des restes chinois