Congruence modulo n

La congruence modulo \( n \) est une relation d’équivalence définie sur l’ensemble des entiers relatifs ℤ. Deux entiers \( a \) et \( b \) sont dits congrus modulo \( n \) si leur différence est un multiple de \( n \) : $$ a\rho b \:\: (mod \: n) \Leftrightarrow a - b = k \cdot n,\ \text{où } k \in \mathbb{Z} $$

Exemple

Exemple 1

Soient \( a = 10 \) et \( b = 4 \). Dire que \( a \) est congru à \( b \) modulo \( n = 2 \) signifie que la différence \( a - b \) doit être divisible par 2 :

$$ a \equiv_n b $$

$$ 10 \equiv_2 4 \Leftrightarrow 10 - 4 = 6 = 3 \cdot 2 $$

La différence \( a - b = 6 \) étant un multiple de 2, la congruence est bien vérifiée.

Exemple 2

Considérons maintenant \( a = 7 \) et \( b = 4 \). Vérifions si \( 7 \) est congru à \( 4 \) modulo 2 :

$$ a \equiv_n b $$

$$ 7 \equiv_2 4 \Leftrightarrow 7 - 4 = 3 = k \cdot 2 $$

Mais il n’existe aucun entier \( k \) tel que \( 2k = 3 \). La différence n’étant pas divisible par 2, la congruence n’est donc pas satisfaite.