Congruences

Plan du chapitre "Arithmétique dans ℤ"

Congruence modulo un entier sur {\mathbb{Z}}

Définition
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}}.
Proposition
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 {\{a+kn,\;k\in\mathbb{Z}\}}.

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 {\{0,\ldots,n-1\}}, 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}=\{\overline{0},\overline{1},\ldots,\overline{n-1}\}}.

Opérations sur les congruences

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :

Page précédente : nombres premiers
Retour au début : divisibilité et division euclidienne