Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
180 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Le lemme chinois en termes de congruences next up previous contents
suivant: Systèmes de congruences monter: bad précédent: Interprétation géométrique   Table des matières

Le lemme chinois en termes de congruences

Lemme [lemme chinois]Soient $ n_1, n_2\geq 2$ deux entiers premiers entre eux et $ u_1 n_1 + u_2 n_2= 1$ une équation de Bézout. Soient $ a_1, a_2\in{\mbox{\bf Z}}$ et $ a\in{\mbox{\bf Z}}$ tel que $ a\equiv a_1 u_2 n_2 + a_1 u_1 n_1 (n_1 n_2)$. Alors pour $ x\in{\mbox{\bf Z}}$ on a l'équivalence

\begin{displaymath}
\left.
\begin{array}{ccc}
x & \equiv & a_1\; (n_1) \\
x & \...
...ray}\right\}
\;
\Longleftrightarrow
\;
x \equiv a\;(n_1 n_2).
\end{displaymath}

Remarque 24   On peut réinterpréter le lemme en disant que la solution générale $ x\in{\mbox{\bf Z}}$ du système de congruences à gauche est donnée par

$\displaystyle x=a+k n_1 n_2\: , \;k\in{\mbox{\bf Z}}.
$


Démonstration. Vérifions d'abord que $ a$ est bien une solution du système de congruences. En effet, d'après l'hypothèse, nous avons

$\displaystyle a= a_1 u_2 n_2 + a_2 u_1 n_1 + k n_1 n_2
$

pour un $ k\in{\mbox{\bf Z}}$ et donc

$\displaystyle a \equiv a_1 u_2 n_2 \equiv a_1 (u_2 n_2 + u_1 n_1) \equiv a_1 \;(n_1)
$

et de même

$\displaystyle a\equiv a_2 u_1 n_1 \equiv a_2 (u_1 n_1 + u_2 n_2) \equiv a_2 \; (n_2).
$

Montrons maintenant l'équivalence. Supposons que $ x\equiv
a \; (n_1 n_2)$. Alors $ x=a+k n_1 n_2$ pour un $ k\in{\mbox{\bf Z}}$ et donc $ x\equiv a \equiv a_1\;(n_1)$ et $ x \equiv a \equiv a_2\;(n_2)$. Réciproquement, supposons que $ x$ vérifie $ x\equiv a_1\;(n_1)$ et $ x\equiv a_2 \;(n_2)$. Alors nous avons $ (x-a) \equiv 0\;(n_1)$ et $ (x-a)\equiv 0\;(n_2)$. Donc $ x-a$ est divisible par $ n_1$ et par $ n_2$. Puisque les deux sont premiers entre eux, il s'ensuit (lemme de Gauss) que $ x-a$ est divisible par $ n_1 n_2$, c'est-à-dire que $ x\equiv
a \; (n_1 n_2)$. $ \surd$

Exemple 25   Considérons le système
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 1\;(17)$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 2\;(28)$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 3\;(31)$  

Nous avons l'équation de Bézout $ 5\times 17 - 3 \times 28=1$. Le système formé des deux premières équations est donc équivalent à la congruence $ x\equiv a\;(17\times 28)$ $ a=1 \times (-3\times 28) + 2\times (5\times 17)= 86$. Le système des trois équations se réduit donc à
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 86 \; (476)$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 3 \; (31).$  

Nous avons l'équation de Bézout $ (-14)\times 476 + 215\times 31=1$. Donc le système est équivalent à la congruence $ x\equiv b\;(476\times 31)$ $ b= 86\times (215\times 31) +3 \times (-14\times 476)= 553198$. Si nous réduisons $ b$ modulo $ 476\times 31= 14756$, nous trouvons que le système des trois équations est équivalent à la congruence

$\displaystyle x \equiv 7226 \; (14756);
$

Nous invitons le lecteur à vérifier que $ 7226$ donne les restes $ 1$, $ 2$ et $ 3$ dans la division par $ 17$, $ 28$ et $ 31$.


next up previous contents
suivant: Systèmes de congruences monter: bad précédent: Interprétation géométrique   Table des matières
Bernhard_Keller
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page