Les congruences

I. Définition

Soit $n$ un entier naturel supérieur ou égal à 2, et $a, b$ deux entiers relatifs.

On dit que $a$ et $b$ sont congrus modulo $n$ si, et seulement si, $a$ et $b$ ont le même reste dans la division par $n$.

On note alors : $a \equiv b \mod n$ ou $a \equiv b (n)$ ou $a \equiv b [n]$.

Exemples

$\circ\quad$ $57 = 7 \times 8 + 1$ et $15 = 7 \times 2 + 1$, donc $57 \equiv 15 [7]$.

$\circ\quad$ $41 = 9 \times 4 + 5$ et $-4 = 9 \times (-1) + 5$, donc $41 \equiv -4 [9]$.

Remarques

$\circ\quad$ Un nombre est congru à son reste dans la division euclidienne par $n$ :
$2019 \equiv 9 [10]$,
$17 \equiv 1 [4]$.

$\circ\quad$ La parité s’exprime par :
$x \equiv 0 [2]$ si $x$ est pair,
$x \equiv 1 [2]$ si $x$ est impair.

$\circ\quad$ $n$ est un diviseur de $a$ si, et seulement si, $a \equiv 0 [n]$.

II. Propriété : Relation d’équivalence

La congruence est une relation d’équivalence, c’est-à-dire que pour tous entiers $a, b, c$ :

$\circ\quad$ Réflexivité : $a \equiv a [n]$.

$\circ\quad$ Symétrie : Si $a \equiv b [n]$, alors $b \equiv a [n]$.

$\circ\quad$ Transitivité : Si $a \equiv b [n]$ et $b \equiv c [n]$, alors $a \equiv c [n]$.

Théorème

Soit $n$ un entier naturel tel que $n \geq 2$, et $a, b$ deux entiers relatifs.

$a \equiv b [n] \Leftrightarrow a - b \equiv 0 [n]$.

Théorème

Soit $n$ un entier naturel tel que $n \geq 2$, et $a, b$ deux entiers relatifs.

$\boxed{a \equiv b [n] \Leftrightarrow a - b \equiv 0 [n]}$

Démonstration

On démontre l’équivalence par double implication.

$\Rightarrow$ Supposons que $a \equiv b [n]$.

Il existe alors deux entiers relatifs $q$ et $q'$ tels que :

$a = nq + r$
$b = nq' + r$ avec 0 \leq r < n .

Par soustraction terme à terme :

$a - b = nq - nq' = n(q - q')$.

Donc $(a - b)$ est un multiple de $n$, d’où $a - b \equiv 0 [n]$.

$\Leftarrow$ Réciproquement, supposons que $a - b \equiv 0 [n]$, donc il existe un entier relatif $k$ tel que : $a - b = k n$.

La division euclidienne de $a$ par $n$ donne :

$a = nq + r$ avec 0 \leq r < n .

On a donc :

$nq + r - b = kn \Leftrightarrow -b = kn - nq - r \Leftrightarrow b = (q - k)n + r$.

Ce qui entraîne : $a \equiv b [n]$.

Théorème

Soit $n$ un entier naturel ($n \geq 2$) et $a, b, c, d$ des entiers relatifs vérifiant :

$a \equiv b [n]$ et $c \equiv d [n]$.

La relation de congruence est compatible avec :

$\circ\quad$ L’addition :
$a + c \equiv b + d [n]$.

$\circ\quad$ La multiplication :
$ac \equiv bd [n]$.

$\circ\quad$ Les puissances :
$a^k \equiv b^k [n]$, pour tout $k \in \mathbb{N}$.

III. Exemples rédigés et méthodes

$1.$ Utiliser un tableau de congruence.

Déterminer les restes de la division euclidienne pour $n \in \textbf{N}$ de $3^n$ par 7.

Il est bon de rappeler que pour tout $x \in \textbf{Z}$, $r$ est le reste de la division euclidienne de $x$ par 7 si $r \in \lbrace 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 \rbrace$ et $x \equiv r~[7]$
On dresse le tableau qui permet de montrer les restes modulo 7 des premières puissances de 3 :

Pour tout $k \in \textbf{N}$, $3^{6k} \equiv (3^6)^k \equiv 1~[7]$
Soit $n \in \textbf{N}$, il existe $(q~;r) \in \textbf{N} \times \textbf{N}$ tel que $n = 6q + r$ avec 0 \leq r < 6
$r \in \lbrace 0 ; 1 ; 2 ; 3 ; 4 ; 5 \rbrace$ et comme $3^n = 3^{6q+r} = (3^6)^q \times 3^r$, on a :
$3^n \equiv 3^r [7]$
Si $n = 6q$, on a : $3^n \equiv 1(7)$ : le reste est 1.
Si $n = 6q + 1$, on a : $3^n \equiv 3(7)$ : le reste est 3.
Si $n = 6q + 2$, on a : $3^n \equiv 2~(7)$ : le reste est 2.
Si $n = 6q + 3$, on a : $3^n \equiv 6~(7)$ : le reste est 6.
Si $n = 6q + 4$, on a : $3^n \equiv 4~(7)$ : le reste est 4.
Si $n = 6q + 5$, on a : $3^n \equiv 5~(7)$ : le reste est 5.

$2.$ Déterminer un reste dans une division euclidienne

Déterminer le reste de la division euclidienne par 7 de $1515^{2000}$

Solution :
$1515 = 7 \times 216 + 3$, donc $1 515 \equiv 3~(7)$.
Donc, pour tout $n \in \textbf{N} , \, \, 1515^n \equiv 3^n$
Pour $n = 2000$, on effectue la division euclidienne de 2000 par 6 : $2 000 = 6 × 333 + 2$.
Précédemment, on a vu que $3^{2000} \equiv 2~(7)$
Donc $1515^{2000} \equiv 2~(7)$
Le reste de la division euclidienne de $1515^{2000}$ par 7 est 2.