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
171 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 next up previous contents
suivant: Classes de congruence inversibles monter: bad précédent: Le lemme chinois en   Table des matières

Systèmes de congruences


Soient $ r$ 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 $ x=a$ et $ x=a'$ sont deux solutions. Alors la différence $ a-a'$ est divisible par tous les $ n_i$ et donc par leur plus petit commun multiple $ n=$PPCM $ (n_1, \ldots, n_r)$. Donc s'il existe une solution, sa classe modulo $ n$ 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 $ c$ pour lesquels le sytème admet des solutions et de calculer les solutions dans ce cas. Constatons tout d'abord que les nombres $ 18$ et $ 12$ 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 $ d$ de $ n$ (en effet, si $ n=q d$ et $ a=b+k n$ alors $ a=b+(k q) d$). 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 $ x$ tels que $ x \equiv 3c+12 \;(36)$.


next up previous contents
suivant: Classes de congruence inversibles monter: bad précédent: Le lemme chinois en   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
Autres...