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
153 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
 
 
 
 
 
Congruences next up previous contents
suivant: Critères de divisibilité monter: bad précédent: La division euclidienne et   Table des matières

Congruences


Définition Soient $ n\geq 1$ un entier et $ a,b\in{\mbox{\bf Z}}$. On dit que $ a$ est congru à $ b$ modulo $ n$ s'il existe un $ k\in{\mbox{\bf Z}}$ tel que $ a=b+k n$. On écrit alors

$\displaystyle a\equiv b\;(n)$    ou $\displaystyle a\equiv_n b$    ou $\displaystyle a = b $   mod$\displaystyle  n.
$

Remarque 17   On a $ a\equiv b\;(n)$ si et seulement si $ a$ et $ b$ ont le même reste dans la division euclidienne par $ n$. En effet, si nous avons $ a=qn+r$ et $ b=q' n+r$, alors $ a=b +(q-q') n$ et $ a\equiv b\;(n)$. Réciproquement, si $ a=q n+r$ et $ b=q'  n+r'$ et que $ a=b+k n$, alors

$\displaystyle a=b+k n=q'  n +r'+k n= (q'+k) n +r' = q n + r
$

et par l'unicité de la division euclidienne, il s'ensuit que $ r=r'$ (et $ q=q'+k$).

Exemple 18   Nous avons $ 6\equiv -15\;(7)$ car $ 6=-15+3\times 7$. Notons que $ -15$ a effectivement le même reste que $ 6$ pour la division euclidienne par $ 7$ car $ -15=(-3)\times 7+6$.

Lemme

a)
La relation $ \equiv_n$ est une relation d'équivalence.
b)
Si $ a\equiv a'\;(n)$ et $ b\equiv b'\;(n)$, alors $ a+b\equiv a'+b'\;(n)$ et $ a b \equiv a' b'\;(n)$. Dans ce cas, on a aussi $ a^m\equiv a'^m\;(n)$ pour tout $ m\in{\mbox{\bf N}}$.
c)
Les nombres $ 0,1,\ldots, n-1$ forment un système de représentants des classes par rapport à $ \equiv_n$.


Démonstration. a) La relation est réflexive car nous avons $ a=a+0\times n$ pour tout $ a\in{\mbox{\bf Z}}$. Elle est symétrique car si nous avons $ a=b+k n$ alors nous avons $ b=a+(-k) n$. Elle est transitive, car si nous avons $ a=b+k n$ et $ b=c+l n$, alors nous avons $ a=(c+l n)+k n=c+(l+k) n$.

b) Supposons que $ a=a'+k n$ et que $ b=b'+l n$. Alors $ a+b=a'+b'+(k+l) n$ et

$\displaystyle a b=(a'+k n)(b'+l n)=a' b'+a'ln+knb'+klnn= a' b'+(a'l+kb'+kln) n.
$

La dernière affirmation s'ensuit par récurrence sur $ m$.

c) Tout $ a\in{\mbox{\bf Z}}$ est équivalent par $ \equiv_n$ à un et un seul des nombres $ 0,1,\ldots, n-1$. En effet, cette affirmation est une reformulation de l'existence et de l'unicité du reste dans la division euclidienne de $ a$ par $ n$.$ \surd$

Définition On pose

$\displaystyle {\mbox{\bf Z}}/n{\mbox{\bf Z}}\;= \; {\mbox{\bf Z}}/\equiv_n.
$

On note   $ ^n\overline {a}$ ou $ \overline {a}$ (ou même $ a$) la classe de $ a\in{\mbox{\bf Z}}$. Les éléments de $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$ sont donc les $ \overline {a}$, $ a\in{\mbox{\bf Z}}$. On munit $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$ des deux lois
$\displaystyle +\;: {\mbox{\bf Z}}/n{\mbox{\bf Z}}\times {\mbox{\bf Z}}/n{\mbox{\bf Z}}\stackrel{ }{\longrightarrow} {\mbox{\bf Z}}/n{\mbox{\bf Z}},$   $\displaystyle (\overline {a}, \overline {b}) \mapsto \overline {a}+\overline {b}:= \overline {a+b}$  
$\displaystyle \cdot\;: {\mbox{\bf Z}}/n{\mbox{\bf Z}}\times {\mbox{\bf Z}}/n{\mbox{\bf Z}}\stackrel{ }{\longrightarrow} {\mbox{\bf Z}}/n{\mbox{\bf Z}},$   $\displaystyle (\overline {a}, \overline {b}) \mapsto \overline {a}\cdot\overline {b}:= \overline {a\cdot b}$  

Exemple 19   Grâce au lemme ci-dessus les deux lois sont bien définies.

Par définition de la notion de `classe d'équivalence', nous avons

     $\displaystyle ^n\overline {a} =$     $\displaystyle ^n\overline {b}$    si et seulement si $\displaystyle a\equiv b\;(n).
$

Par conséquent, deux classes $ \overline {a}$ et $ \overline {b}$ sont égales ssi les restes de $ a$ et $ b$ par la division euclidienne par $ n$ sont égaux.

D'après le lemme ci-dessus, les classes

$\displaystyle \overline {0}, \overline {1}, \ldots, \overline {n-1}
$

sont distinctes deux à deux et toute classe est égale à une d'entre elles. Ces classes constituent donc la liste (exhaustive et sans répétitions) des éléments de $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$. En particulier, $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$ est de cardinal $ n$.


next up previous contents
suivant: Critères de divisibilité monter: bad précédent: La division euclidienne et   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