On sait que si a est un entier relatif non nul,  alors pour tout b dans Z il existe Q et R uniques entiers vérifiant :

b = Q.a + R
0 < R < |a|.

C'est le principe de la division euclidienne. Q est le quotient et R le reste de la division euclidienne de b par a.

Définition
On dit que deux entiers relatifs n est congrus à m modulo a ou que n est égal à m modulo a si et seulement si leurs restes respectifs dans la division euclidienne par a sont égaux.
Par exemple , on a -10 = 4*3 + 2   et   8 = 2*3 + 2. -10 et 8 ont donc même reste dans le division euclidienne par 3, ils sont égaux modulo 3 ou congrus modulo 3.
Notation: n m [a]   On peut donc écrire que -10 8 [3].
On remarque que n m [a] si et seulement si (n - m) est divisible par a

Propriété 1 de la Congruence:

Si n m [a] alors m n [a].  On dit que la congruence est une relation symétrique.
Si n m [a] et m k [a] alors n k [a]. C'est une relation transitive.
n n [a]. C'est une relation reflexive.

Une relation possédant ces trois propriétés est appelée "Relation d'Equivalence".
On peut alors former une partition sur l'ensemble des entiers relatifs Z en considérant, pour tout entier R compris entre 0 et |a|-1, le sous-ensemble formé des entiers relatifs admettant R comme reste dans le division euclidienne par a. C'est aussi l'ensemble des entiers relatifs qui sont congrus à R modulo a.

Par exemple, si a = 5, on a

etc ....

La relation de congruence est compatible avec l'addition et la multiplication, c'est à dire que :
Propriété 2:
Si m n [a] et k h [a] alors (m + k) ( m + h) [a] et  (n.k) (m.h) [a]
Ceci se vérifie sans peine en utilisant le fait que n m [a] si et seulement si (n - m) est divisible par a

On en déduit alors:
Si m n [a] alors pour tout entier k > 0, on a m^k n^k [a]
Exemples d'utilisation:
Exemple 1
Si on cherche le reste de la division euclidienne de 10⁵ par 7, on remarque
que l'on a : 10 3 [7] donc 10² 9 [7] ou encore 10² 2 [7]
Donc 10³ 6 [7] donc 10⁴ 18 [7] ou encore 10⁴ 4 [7] et donc 10⁵ 12 [7]
C'est à dire 10⁵ 5 [7].

Exemple 2
Si on cherche une condition nécessaire et suffisante pour qu'un entier soit divisible par 3, il suffit de remarquer que l'écriture d'un entier en base 10 est du type:

où les ai sont des entiers compris entre 0 et 9.
Cette écriture signifie que l'on a :
n = 10^ka_k  + 10^k-1a_k-1 + ... + 10²a₂ + 10a₁ + a₀
Or , 10 1 [3] donc pour tout entier i, on a : 10ⁱ 1 [3].
On en déduit alors que :
10^ka_k  + 10^k-1a_k-1 + ... + 10²a₂ + 10a₁ + a₀   a_k  + a_k-1 + ... + a₂ + a₁ + a₀ [3]
On retrouve alors le résultat classique suivant:
UN NOMBRE ENTIER EST DIVISIBLE PAR 3 si et seulement si
LA SOMME DES SES CHIFRRES EN BASE 10 EST ELLE-MEME DIVISBLE PAR 3.

Exemple 3
Montrez que pour tout n entier, n⁷ + 6n est divisible par 7.
Il suffit de montrer que n⁷ + 6n 0 [7]. Or comme 6 -1 [7], il suffit de montrer que
n⁷ - n 0 [7]  ou  encore n⁷ n [7], égalité qu'il suffit alors de montrer pour n compris entre 0 et 6.
Pour n = 0 et n = 1, c'est évident.
Pour n = 2, comme 2³ = 8 , on a 2³ 1 [7] et donc, comme 2⁷ = 2³.2, on a bien 2⁷ 2 [7].
Pour n = 3, on a 3² = 9 donc 3² 2 [7].  D'où 3⁶ 2³ [7] ou encore 3⁶ 1[7] et donc 3⁷ 3 [7].
Pour n = 4, on a 4² = 16 donc 4² 2 [7]. C'est la même situation que n=3.
Pour n = 5, on a 5² = 25 donc 5² 4 [7] donc 5⁶ 2⁶ [7] d'où 5⁶ 1 [7] et donc 5⁷ 5 [7] .
Pour n = 6, il suffit devoir que 6 = 2*3 , donc 6⁷ 2⁷*3⁷ [7] et donc 6⁷ 6 [7]
On a donc bien pour tout n entier, n⁷ + 6n est divisible par 7.

Exemple 4
Montrez que si un nombre premier p > 2 est de la forme p = a² + b², où a et b sont deux entiers, alors p a pour reste, dans la division euclidienne par 4, R = 1.
Autrement dit, p 1 [4].
On commence par chercher les carrés modulo 4. Pour cela, il suffit d'examiner les cas 0 , 1 , 2 et 3.
Or 0² = 0 , 1² = 1 , 2² = 4 et 3² = 9. Donc les carrés modulo 4 sont : 0 et 1.
Si un nombre entier est un carré alors il est congru à 0 ou 1 modulo 4.
Comme p est un nombre premier > 2, il est impair donc il est est congru à 1 ou 3 modulo 4.
Or, 3 ne peut pas être écrit comme somme de deux carrés modulo 4. ( les sommes possibles sont
0² + 0² , 0² + 1² , 0² + 2² , 0² + 3² , 1² + 2² , 1² + 3² , 2² + 3² et elles sont congrues à 0 ou 1 modulo 4).
Donc, on doit bien avoir p 1 [4].