Congruence dans ℤ

Congruence et division euclidienne

Définition : congruence

$n$ désigne un entier naturel non nul, $a$ et $b$ sont des entiers relatifs.

On dit que $a$ et $b$ sont congrus modulo $n$ lorsque la différence $a - b$ est un multiple de $n$.

• Notations : $a\equiv b\ \text{mod}\ n$ ou $a\equiv b [n]$ ou encore $a\equiv b\ (n)$

Propriétés : lien entre congruence et division euclidienne

• Tout nombre est congru modulo $n$ au reste de sa division euclidienne par $n$.
• $a$ et $b$ sont congrus modulo $n$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
• Si $a\equiv r\ [n]$ avec $n$ exclu $0 ≤ r < n$ alors $r$ est le reste de la division euclidienne de $a$ par $n$.

Transitivité

Propriétés : transitivité

• Si on a $a\equiv b\ [n]$ et $b\equiv c\ [n]$ alors $a\equiv c\ [n]$. C’est la transitivité.
• Si on a $a\equiv b\ [n]$ et $a'\equiv b'\ [n]$ alors :
• $a+a'\equiv b+b'[n]$
• $a-a'\equiv b-b'[n]$
• Si on a $a\equiv b\ [n]$ et $a'\equiv b' [n]$ alors $aa'\equiv bb'[n]$
• Si on a $a\equiv b\ [n]$ alors pour tout $k∈\mathbb Z$, on a : $ka\equiv kb\ [n]$
• Si on a $a\equiv b\ [n]$ alors pour tout $p∈\mathbb N^*$, on a : $a^p\equiv b^p\ [n]$
• Si on a $a\equiv -1\ [n]$ alors $a^p\equiv(-1)^p\ [n]$

Application : écriture des nombres en base b

Propriété :

Soit $b$ élément de $\mathbb N\setminus\lbrace 0\ ;1\rbrace$ :

• Tout entier naturel $n$ peut s’écrire d’une manière unique :

$n=n_pb^p+n_{p-1}b^{p-1}+…+n_1b^1+n_0b^0$

Avec $np≠0$ et pour tout $i$ de $\lbrace 0\ ;1\ ;…;P\rbrace$, $0 ≤ n_i < b$.

• De plus, les chiffres de l’écriture en base $b$ de $n$ sont les nombres $n_p,\ n_{p-1},…,\ n_1\text{ et }n_0$.

  L’écriture en base $b$ de $n$ est : $\overline{n_pn_{p-1}…n_1n_0}^b$