congru

Congruences modulo n dans l'ensemble des entiers relatifs

Soit n un entier naturel non nul .

Considérons dans $\mathbb{Z}$ la relation notée $\equiv$ telle que pour tous entiers relatifs $x$ et $y$ :
$x \equiv y \,(\mod n) \Longleftrightarrow x - y $ est un multiple de $n$ dans $\mathbb{Z}$
$\Longleftrightarrow \exists k \in \mathbb{Z}$ tel que $x - y = kn$

On démontre facilement que cette relation est une relation d'équivalence
et on appelle cette relation congruence modulo $n$ dans $\mathbb{Z} $.
Remarque :
$x \equiv y \,(\mod n)$ se lit : " $x$ est congru à $y$ modulo $n$ ".
Propriété : pour que deux entiers relatifs $x$ et $y$ soient congrus modulo $n$ dans $\mathbb{Z}$ il faut et il suffit qu'ils aient le même reste dans la division euclidienne par $n$.
Choisire $r_1>0$ et $r_2>0$
a-ton $\equiv$ ( ) $?$

propriétés de la congruence modulo $n$ dans $\mathbb{Z}$
Pour tout entiers relatifs $x_1, x_2, y_1, y_2 $ et tout entier naturel non nul $n$ on a :

(*)$\begin{cases} x_1\equiv y_1\,(\mod n) \\[0.5cm] x_2\equiv y_2\,(\mod n) \end{cases}$$\implies$ $\begin{cases} x_1+x_2\equiv y_1+y_2\,(\mod n) \\[0.3cm] x_1\times x_2\equiv y_1\times y_2\,(\mod n) \\[0.3cm] \lambda x_1\equiv y_1\,(\mod \lambda n) \end{cases}$
(**)$\begin{cases} x_1= \lambda x_2 \\[0.3cm] y_1= \lambda y_2 \\[0.3cm] x_1\equiv y_1\,(\mod \lambda n) \end{cases}$$\implies$$ x_2\equiv y_2\,(\mod n)$

Conséquence : caractères de divisibilité d'un nombre

Soit $a$ un entier naturel dont la représentation symbolique dans le système décimal est : $a = a_pa_{p-1} \cdots a_2a_1a_0$, alors :
$a=\displaystyle\sum_{i=0}^{p}a_i 10^i =a_0+a_1\times 10+a_2\times 10^2+\cdots +a_p\times 10^p $
en utilisant les propriétés précédentes on obtient :
$a\equiv a_0\,(\mod 2)$
$a\equiv a_0\,(\mod 5)$
$a\equiv a_0a_1\,(\mod 4)$
$a\equiv a_0a_1\,(\mod 25)$
$a\equiv a_0a_1a_2\,(\mod 8)$
$a\equiv a_0a_1a_2\,(\mod 125)$
$a\equiv a_0+a_1+a_2+\cdots +a_p\,(\mod 3)$
$a\equiv a_0+a_1+a_2+\cdots +a_p\,(\mod 9)$
$a\equiv a_0-a_1+a_2-a_3\cdots +(-1)^pa_p\,(\mod 11)$
ce qui amène aux caractères de divisibilités d'un entier.
Classe Modulo $n$

Congruence et nombre premier :
Si $a$ est premier avec $p$, et si $x$ et $y$ sont des entiers tels que $xa \equiv ya \,(\mod p)$, alors $x\equiv y \,(\mod p)$.

Démonstration :
$xa \equiv ya\, (\mod p)$ donc
$p$ divise $xa - ya = a (x - y)$
or $a$ premier avec $p$ donc $p$ divise $x - y$
donc $x - y \equiv 0 \,(\mod p)$
donc $x \equiv y\; (\mod p)$

Tables de congruence