A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

260 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

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 est congru à modulo s'il existe un $k\in{\mbox{\bf Z}}$ tel que . 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

ont le même reste dans la division euclidienne

par

. En effet, si nous avons

, alors

et $a\equiv b\;(n)$ . Réciproquement, si

et que

, 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

(et

Exemple 18 Nous avons $6\equiv -15\;(7)$ car $6=-15+3\times 7$ . Notons que

a effectivement le même reste que

pour la division euclidienne par

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 alors nous avons . Elle est transitive, car si nous avons et , alors nous avons .

b) Supposons que et que . Alors 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

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 par . $\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

) 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

par la division euclidienne par

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 .