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

Proposition
Soit {n\in\mathbb{N}^*}. Pour tous entiers relatifs {a,b,c,d}, on a les implications :{\begin{cases}a\equiv b~[n]\cr a'\equiv b'~[n]\end{cases}\Rightarrow\begin{cases}a+a'\equiv b+b'~[n]\cr aa'\equiv bb'~[n]\end{cases}}

Pour tout entier naturel {k}, on a l’implication : {a\equiv b~[kn]\Rightarrow a\equiv b~[n]}.

Pour tout entier naturel {k}, on a l’implication : {a\equiv b~[n]\Rightarrow a^{k}\equiv b^{k}~[n]}.

Si {q} est un entier strictement positif, on a l’équivalence : {a\equiv b~[n]\Leftrightarrow qa\equiv qb~[qn]}.

Si les entiers {q} et {n} sont premiers entre eux, alors : {qa\equiv qb~[n]\Rightarrow a\equiv b~[n]}.

Le résultat suivant est très utile :

Proposition (petit théorème de Fermat)
Soit {p} un entier premier. Pour tout entier relatif {a}, on a : {a^{p}\equiv a~[p]}.
En particulier, si {a} n’est pas divisible par {p}, on a : {a^{p-1}\equiv 1~[p]}.

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