La relation de congruence est l’une des bases de l’arithmétique modulaire. Au lieu de considérer les entiers, on raisonne suivant leur reste dans la division euclidienne par un entier fixé.

I) Divisibilité dans ℤ

Définitions : Si a et b sont deux entiers relatifs, on dit que b divise a ou que b est un diviseur de a ou que a est un multiple de b ou que a est divisible par b lorsqu’il existe un entier relatif k tel que $a = k b$ .

On note $b | a$ .

Propriétés

Tout entier relatif non nul n possède un nombre fini de diviseurs, compris entre $- n$ et n.

Soit a, b et c trois entiers relatifs, avec $a \neq 0$ et $b \neq 0$ . Si a divise b et b divise c, alors a divise c.

Mot-clé
ℤ est l’ensemble des entiers relatifs, ℕ est l’ensemble des entiers naturels.
ℕ est inclus dans ℤ, on note $ℕ \subset ℤ$ .

Soit a, b et c trois entiers relatifs, avec $a \neq 0$ . Si a divise b et c, alors a divise tout nombre de la forme $m b + n c$ , où m et n sont des entiers relatifs.

II) Division euclidienne

Soit a un entier relatif et b un entier naturel non nul.

Théorème : Il existe un unique couple $(q; r)$ d’entiers relatifs tels que :

$a = b q + r$ et $0 \leq r < b$ .

Définitions : a est le dividende, b est le diviseur, q est le quotient, r est le reste dans la division euclidienne de a par b.

III) Congruences

Définition : Soit a et b deux entiers relatifs et n un entier naturel non nul. On dit que a et b sont congrus modulo n lorsque a et b ont le même reste dans la division euclidienne par n. On note $a \equiv b (n)$ .

Propriétés : Soit a, $a^{'}$ , b, $b^{'}$ et c des entiers relatifs et n un entier naturel non nul.

a et b sont congrus modulo n si et seulement si $b - a$ est divisible par n.

Si $a \equiv b (n)$ et $b \equiv c (n)$ , alors $a \equiv c (n)$ .

Si $a \equiv b (n)$ et $a^{'} \equiv b^{'} (n)$ , alors $a + a^{'} \equiv b + b^{'} (n)$ et $a a^{'} \equiv b b^{'} (n)$ .

Si $a \equiv b (n)$ alors, pour tout entier relatif c, $a + c \equiv b + c (n)$ .

Si $a \equiv b (n)$ alors, pour tout entier naturel non nul p, $a^{p} \equiv b^{p} (n) .$

Méthodes

1) Construire et utiliser un tableau de congruences

Pour tout entier relatif n, on pose $g (n) = n^{2} - 3 n + 6 .$

On veut déterminer les entiers n tels que $g (n)$ soit divisible par 5.

a. Étudier suivant le reste de n dans la division euclidienne par 5 (on dit « reste de n modulo 5 ») le reste de $g (n)$ modulo 5. Consigner les résultats dans un tableau.

b. Conclure à l’aide du tableau de la question précédente.

Conseils
a. Utilisez les propriétés des congruences.
b. Utilisez l’équivalence « $g (n)$ est divisible par $5 \Leftrightarrow g (n) \equiv 0 (5)$ ».

Solution

a. On peut dresser le tableau suivant.

5, alors $n^{2} - 3 n + 6 \equiv 9 - 9 + 6 (5)$ , donc $g (n) \equiv 6 (5)$ , donc $g (n) \equiv 1 (5)$ .

On raisonne de la même manière pour les autres cas.

b. D’après le tableau précédent, on constate que $g (n) \equiv 0 (5)$ si et seulement si $n \equiv 4 (5)$ . Les entiers n tels que $g (n)$ soit divisible par 5 sont les entiers n de la forme 4 + 5k, avec k entier.

2) Montrer une divisibilité à l’aide de congruences

Montrer que, pour tout entier naturel n, $5^{2 n} - 14^{n}$ est divisible par 11.

Conseils
Utilisez des congruences modulo 11.

Solution

$5^{2} = 25$ , donc $5^{2} \equiv 3 (11)$ $(25 = 11 \times 2 + 3)$ , donc, pour tout entier naturel n, $5^{2 n} \equiv 3^{n} (11)$ (1).

$14 = 11 + 3$ , donc $14 \equiv 3 (11)$ , donc $14^{n} \equiv 3^{n} (11)$ (2).

Des relations (1) et (2) on déduit, par soustraction, que, pour tout entier naturel n, $5^{2 n} - 14^{n} \equiv 0 (11)$ , ce qui signifie que $5^{2 n} - 14^{n}$ est divisible par 11.

Divisibilité et congruences

I) Divisibilité dans ℤ

II) Division euclidienne

III) Congruences

Méthodes

1) Construire et utiliser un tableau de congruences

Solution

2) Montrer une divisibilité à l’aide de congruences

Solution