I. Définition

Soit $n \ge 2$ un entier. On dit que $a$ est congru à $b$ modulo $n$, si $n$ divise $b – a$. On note alors $a \equiv b\left[ n \right]$.
On note aussi parfois $a \equiv b\left( {\bmod n} \right)$ ou $a \equiv b\left( n \right)$.

Une autre formulation est : $a \equiv b\left( {\bmod n} \right)$ $\Leftrightarrow \exists k \in$ $\mathbb{Z}$,  $a = b + kn$

Remarque : $n$ divise a si et seulement si $a \equiv 0\left[ n \right]$.

Les propriétés suivantes sont des conséquences immédiates de la définition

Propriétés
• $a \equiv a\left[ n \right]$ : La relation de congruence modulo $n$ est réflexive ;
• Si $a \equiv b\left[ n \right]$, alors $b \equiv a\left[ n \right]$ : La relation de congruence modulo $n$ est symetrique ;
• Si $a \equiv b\left[ n \right]$ et $b \equiv a\left[ n \right]$, alors $a \equiv c\left[ n \right]$ : La relation de congruence modulo $n$ est transitive.
Soit $n$ un entier naturel non nul, $a$ et $a’$ deux entiers relatifs, $t$ et $r’$ les restes respectifs des divisions euclidiennes de $a$ et $a’$ par $n$.
• On a: $a \equiv a'\left[ n \right]$ $\Leftrightarrow r = r'$
Soit $n$ un entier naturel non nul et $a, a’, b, b’$ quatre entiers relatifs.
• Si $a \equiv a'\left[ n \right]$ et $b \equiv b'\left[ n \right]$ alors $a + b \equiv$ $a' + b'\left[ n \right]$.
• Si $a \equiv a'\left[ n \right]$ et $b \equiv b'\left[ n \right]$ alors $a \times b \equiv$ $a' \times b'\left[ n \right]$
On dit que la congruence modulo $n$ est compatible avec l’addition et la multiplication dans $\mathbb{Z}$
• Si $k$ est un entier naturel non nul, on a $a \equiv a'\left[ n \right]$ $\Leftrightarrow {a^k} \equiv$ $a{'^k}\left[ n \right]$

II. Congruences particulières (Caractères de divisibilité)

a) Divisibilité par 2

Un entier $x$ est divisible par 2 si et seulement si son chiffre des unités simples est pair, c'est-à-dire si l’entier $x$ se termine par 0 ; 2 ; 4 ; 6 ou 8.

b) Divisibilité par 3 et par 9

Un entier $x$ est divisible par 3 (respectivement par 9 ) si et seulement si la somme de ces chiffres est divisible par 3 ( respectivement par 9 ).

c) Divisibilité par 5

Un entier $x$ est divisible par 5 si et seulement il se termine par 0 ou 5.

d) Divisibilité par 11

Un entier N est divisible par 11 si et seulement si la différence de la somme des chiffres de rang pair et de la somme des chiffres de rang impair est divisible par 11.

e) Divisibilité par 4 et par 25

Un entier $x$ est divisible par 4 (respectivement par 25) si et seulement si le nombre formé par les deux derniers chiffres est divisible par 4 (respectivement par 25).
(A démontrer dans la partie exercice)

III. Petit théorème de Fermat

Si $p$ est un nombre premier et $a \in$ $\mathbb{Z}$ alors : $${a^p} \equiv a\left[ p \right]$$

Corollaire : Si $p$ ne divise pas $a$ alors : $${a^{p - 1}} \equiv 1\left[ p \right]$$

$p$ divise $C_k^p =$ $\frac{{p!}}{{k!\left( {p - k} \right)!}}$ pour $1 \le k \le p - 1$, c’est-à-dire $C_k^p \equiv 0\left[ p \right]$
Démonstration :
En effet, $C_k^p =$ $\frac{{k!}}{{p!\left( {k - r} \right)p!}}$ donc $p! = k!$ $\left( {p - k} \right)!C_k^p$ ainsi $p|k!$ $\left( {p - k} \right)!C_k^p$. Or comme $1 \le k \le p - 1$ alors $p$ ne divise pas $k!$ ( sinon $p$ divise l’un des facteurs de $k !$ or, ils sont tous supérieures à $p$). De même $p$ ne divise pas $\left( {p - k} \right)!$ donc $p$ devise $C_k^p$.

IV. Congruence et Structure d’anneau (Ensemble $\mathbb{Z}$ $/n$ $\mathbb{Z}$)

IV.1 Classe d’équivalence modulo $n$

a) Définition :

Lorsqu'un nombre quelconque $n$ de $\mathbb{Z}$ est divisé par un entier naturel $n$, les restes possibles sont : 0, 1 , 2 ,…, n-1.
On dit qu'un élément $x$ de $\mathbb{Z}$ appartient à la classe $p$modulo $n$ : si : $x \equiv p$ avec $n - 1 \ge 0$.
D’une manière générale, si $x$ est un élément de $\mathbb{Z}$, alors la classe de $x$ modulo $n$ est l’ensemble de tous les éléments de $\mathbb{Z}$ qui ont le même reste que $x$ dans la division par $n$ ; on le note $cl\left( x \right) = \dot x$ tel que $cl\left( x \right) = \dot x$ $= \{ y \in$ $\mathbb{Z}$ $/x - y \equiv 0\left[ n \right]\}$
b) Ensemble quotient $\mathbb{Z}$ $/n$ $\mathbb{Z}$
L'ensemble des classes $p$modulo $n$ est noté par $\mathbb{Z}$ $/n$ $\mathbb{Z}$ et s’appelle groupe quotient de $\mathbb{Z}$ $/n$ $\mathbb{Z}$ tel que : $\mathbb{Z}$ $/n$ $\mathbb{Z}$ $= \{ \dot 0;\dot 1;\dot 2;$ $...;\overbrace {n - 1}^.\}$.

IV.2) Propriétés dans $\mathbb{Z}$ $/n$ $\mathbb{Z}$

a) Propriétés (Addition)

1) L'associativité : $\dot x + \left( {\dot y + \dot z} \right)$ $= \left( {\dot x + \dot y} \right) + \dot z$
2) La commutativité : $\dot x + \dot y =$ $\dot y + \dot x$
3) L'élément neutre : ${\dot 0}$ ( car $\dot x + \dot 0 = \dot x$ )
4) L’élément $\overbrace { - x}^.$, symétrique $x$

b) Propriétés (Multiplication)

1) L'associativité : $\dot x \times \left( {\dot y \times \dot z} \right)$ $= \left( {\dot x \times \dot y} \right) \times \dot z$
2) La commutativité : $\dot x \times \dot y =$ $\dot y \times \dot x$
3) L'élément neutre : 1
4) La distributivité par rapport à l'addition, soit : $\dot x \times \left( {\dot y + \dot z} \right)$ $= \left( {\dot x \times \dot y} \right) +$ $\left( {\dot x \times \dot z} \right)$
On dit qu'un anneau commutatif unitaire A est intègre si pour tout $x$, $y$ de A, on a : $x \times y = 0 \Rightarrow$ $\left\{ \begin{array}{l}x = 0\\y = 0\end{array} \right.$
Lorsque l'anneau n'est pas intègre, il existe $x$ et $y$, tous non nuls, dont le produit est zéro. On dit alors que $x$ et $y$ sont des diviseurs de zéro.