Congruences

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 {\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\}}.

Opérations sur les congruences

Ce contenu nécessite une souscription active.

Retour à l’accueil du cours

Sommaire du chapitre 10

  1. Divisibilité et division euclidienne
  2. Pgcd et algorithme d’Euclide
  3. Entiers premiers entre eux
  4. Nombres premiers
  5. Congruences