Congruence modulo un entier sur {\mathbb{Z}}
Soit {n} un entier strictement positif. Soit {a,b} deux entiers relatifs quelconques.
On note {a\equiv b~[n]} si la différence {b-a} est dans {n\mathbb{Z}} (c’est-à-dire est un multiple de {n}).
On exprime cette situation en disant que {a} et {b} sont congrus modulo {n}.
On définit ainsi une relation sur {\mathbb{Z}}, appelée relation de congruence modulo {n}.
Définitions équivalentes
-
On a l’équivalence : {a\equiv b~[n]\;\Leftrightarrow\;(\exists\, k\in\mathbb{Z},\; a=b+kn)}.
-
De même : {a\equiv b~[n]} équivaut à « {a} et {b} ont le même reste dans la division par {n} ».
Soit {n} un entier strictement positif.
La relation de congruence modulo {n} est une relation d’équivalence sur {\mathbb{Z}}.
Classes d’équivalences
Soit {n} un entier strictement positif fixé.
On note souvent {\overline{a}} la classe d’équivalence de {a} pour la relation de congruence modulo {n}, c’est-à-dire l’ensemble des {b} de {\mathbb{Z}} tels que {b\equiv a~[n]}, c’est-à-dire l’ensemble {\left\{a+kn,\;k\in\mathbb{Z}\right\}}.
Avec ces notations, {\overline{0}=\overline{n}} est l’ensemble de tous les multiples de {n} dans {\mathbb{Z}}.
Tout entier relatif {a} est congru, modulo {n}, à un unique entier {r} de {\left\{0,\ldots,n-1\right\}}, l’entier {r} étant le reste dans la division de {a} par {n}.
Il y a donc exactement {n} classes d’équivalences, et on note souvent {\mathbb{Z}/n\mathbb{Z}=\left\{\overline{0},\overline{1},\ldots,\overline{n-1}\right\}}.