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.

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...) 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 d'après le théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) 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 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

  • n = 3 \times 5 \times 7
  • 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...) à 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...) autre nombre (La notion de nombre en linguistique est traitée à l’article « 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...)

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...) 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...) pour que sa r-ième dent (Une dent est un organe enveloppé d'os, dur, blanchâtre, généralement...) 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...) 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. GeoplanPpcm.png

On peut comprendre simplement pourquoi le calcul sur des roues dentées fait intervenir de l'arithmétique modulaire (En mathématiques et plus précisément en théorie algébrique des nombres,...), en remarquant que l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 Z/nZ.

Utilisations

Le théorème des restes chinois (Le théorème des restes chinois est un résultat d'arithmétique modulaire...) 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...), il intervient aussi dans L'algorithme de Silver-Pohlig-Hellman (en) pour le calcul du logarithme (En mathématiques, une fonction logarithme est une fonction définie sur à valeurs dans ,...) discret.

Il permet de représenter de grands nombres entiers comme n-uplets de restes de divisions euclidiennes. Sous cette forme, des opérations comme l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la...) ou la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire...) peuvent se faire en parallèle en temps (Le temps est un concept développé par l'être humain pour appréhender le...) constant (pas de propagation de retenue). Par contre, la comparaison ou la division (La division est une loi de composition qui à deux nombres associe le produit du premier par...) ne sont pas triviales.

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 (Un polynôme, en mathématiques, est la combinaison linéaire des produits de...) 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.

Page générée en 0.055 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