A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

76 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

Systèmes de congruences

suivant: Classes de congruence inversibles monter: bad précédent: Le lemme chinois en Table des matières

Systèmes de congruences

Soient et $n_1, \ldots, n_r$ des entiers $\geq 2$ et $a_1, \ldots, a_r$ des entiers quelconques. Considérons le système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle a_1 \; (n_1)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle a_2 \; (n_2)$
	$\displaystyle \vdots$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle a_r \; (n_r).$

Supposons que

sont deux solutions. Alors la différence

est divisible par tous les

et donc par leur plus petit commun multiple

PPCM $(n_1, \ldots, n_r)$ . Donc s'il existe une solution, sa classe modulo

est unique.

Il peut ne pas exister de solution comme le montre l'exemple du système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 1 \; (6)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 2 \; (8)$

ou encore celui du système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 1 \;(2)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 0 \;(2) .$

Notons que nous n'avons pas exclu ce genre de contradictions banales.

L'application systématique du lemme chinois nous permettra de réduire tout système de congruences soit à un système contradictoire soit à une seule congruence modulo le plus petit commun multiple des modules. Nous ne développons pas ici la méthode dans le cas général mais nous limitons à la décrire dans un exemple simple.

Considérons le système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 3 \; (18)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (12).$

Il s'agit de déterminer tous les entiers

pour lesquels le sytème admet des solutions et de calculer les solutions dans ce cas. Constatons tout d'abord que les nombres

ne sont pas premiers entre eux de façon que le lemme chinois ne s'applique pas immédiatement. Pour résoudre le problème, nous allons dans une première étape augmenter le nombre d'équations pour obtenir des modules qui sont des puissances de nombres premiers. Nous avons ainsi $18=2\times 3^2$ et d'après le lemme chinois la première congruence est équivalente au système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 1 \;(2)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 3 \; (9) .$

De même, puisque nous avons $12=3\times 4$ , la seconde congruence est équivalente au système

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (3)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (4).$

Nous avons ainsi trouvé un système de quatre congruences qui est équivalent au système de départ. Nous le réécrivons dans un ordre où les puissances de chaque nombre premier sont regroupées ensemble et les puissances les plus élevées apparaissent en premier lieu :

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (4)$	(10.1)
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 1 \;(2)$	(10.2)
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 3 \; (9)$	(10.3)
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (3)$	(10.4)

Rappelons-nous que si nous avons $a\equiv b\;(n)$ alors nous avons aussi $a\equiv b \;(d)$ pour tout diviseur

(en effet, si

alors

). L'équation (

) implique donc que $x \equiv c \;(2)$ de façon que les équations (

) et (

) sont contradictoires sauf si $c\equiv 1\;(2)$ . De même, les équations (

) et (

) sont contradictoires sauf si $c\equiv 0\;(3)$ . Nous avons donc les conditions

$\displaystyle c$	$\displaystyle \equiv$	$\displaystyle 1 \;(2)$
$\displaystyle c$	$\displaystyle \equiv$	$\displaystyle 0 \; (3)$

qui sont nécessaires pour qu'une solution existe. Réciproquement, ces conditions sont aussi suffisantes car si elles sont vérifiées, la congruence (

) est une conséquence de (

), et (

) est une conséquence de (

) de façon que le système tout entier est équivalent à un système de deux congruences

$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle c \; (4)$
$\displaystyle x$	$\displaystyle \equiv$	$\displaystyle 3 \; (9)$

Nous avons l'équation de Bézout $-2\times 4 + 9 =1$ . Donc, d'après le lemme chinois, ce système est équivalent à la congruence $x \equiv c\times 9 + 3 \times (-8) \;(36)$ ou encore $x \equiv 3c+12 \;(36)$ . En conclusion, le système de départ admet une solution si et seulement si $c\equiv 3\;(6)$ et dans ce cas l'ensemble des solutions est l'ensemble des entiers tels que $x \equiv 3c+12 \;(36)$ .