Soit $a$ un entier relatif et $b$ un entier naturel.
Il existe un unique couple ($q$,$r$) avec $q$ et $r$ entiers naturels, tel que :

• $a=bq+r$ avec $0 \leq r < b$.

Il s’agit de la division euclidienne de $a$ par $b$.

On note $a$ le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste.

Il s’agit simplement de la division telle qu’on la connaît !

La division euclidienne de $54$ par $21$ est : $54=2 \times 21+2$.

Le dividende est $54$, le diviseur est $21$, le quotient est $2$ et le reste est $2$.

Soit $n$ un entier naturel supérieur à $2$, et $a$ et $b$ deux entiers relatifs.

• Si $a$ et $b$ ont le même reste par la division euclidienne par $n$, alors $a$ et $b$ sont congrus modulo $n$. 

On écrit alors :

• $a\equiv b \ [n]$

qui se lit : « $a$ est congru à $b$ modulo $n$ ».

$a$ est congru à $b$ modulo $n$ si et seulement si  $a-b$ divise $n$.

Cela s'écrit :

• $a\equiv b \ [n]$ $\Leftrightarrow$ $a-b \mid n$.

La congruence est :

1. réfléxive : $\forall a\in Z$, $\forall n \in N$, $a\equiv a \ [n]$ ;
2. symétrique : si $a\equiv b \ [n]$, alors $b \equiv a \ [n]$ ;
3. transitive : si $a\equiv b \ [n]$ et $b\equiv c \ [n]$, alors $a \equiv c \ [n]$.

Si $a=bn+r$, alors $a \equiv r \ [n]$.

Soient $a$, $b$, $c$ et $d$ 4 entiers relatifs et $n$ un entier naturel, tels que

• $a \equiv b \ [n]$ et $c \equiv d \ [n]$. 

On a :

• $a+c \equiv b+d$ $[n]$ et $a - c \equiv b - d$ $[n]$
• $a \times c \equiv b \times d$ $[n]$
• $\forall k \in N, a^{k} \equiv b^{k} \ [n]$

Pour déterminer le modulo $7$ de $50$ :

• la division euclidienne de $50$ par $7$ donne $50 = 7 \times 7+1$. Donc le reste de la division euclidienne de $50-1$ par $7$ est nul.
• D’après le théorème 1), $49 \equiv 0 \ [n]$ or $1 \equiv 1 \ [n]$, donc par la propriété 1) du théorème 2), $50 \equiv \ [7]$.

Pour déterminer le reste de la division euclidienne de $49^{120}$ par $6$ :

• on a $49 = 8 \times 6 +1$ donc $49 \equiv 1 [6]$.
• Donc, avec la propriété 3) du 2nd théorème sur la congruence, $49^{120} \equiv 1^{120}$, soit $49^{120} \equiv 1 [6]$.
• Le reste vaut donc $1$.