A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

170 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

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 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 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

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

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

est divisible par

et par

. Puisque les deux sont premiers entre eux, il s'ensuit (lemme de Gauss) que

est divisible par

, 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)$ où $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)$ où $b= 86\times (215\times 31) +3 \times (-14\times 476)= 553198$ . Si nous réduisons