Divisibilité, division euclidienne et congruences

Ce que tu sais déjà. En Seconde, tu as manipulé multiples, diviseurs et parité (Seconde — Multiples, diviseurs et parité) ; en Terminale, tu sais raisonner par récurrence (Terminale — Raisonnement par récurrence). L’arithmétique des maths expertes étudie les entiers relatifs pour eux-mêmes : c’est la base de la cryptographie, des codes de contrôle (ISBN, IBAN, numéro de Sécurité sociale) et de nombreuses énigmes.

1. Divisibilité dans les entiers relatifs

Définition. Soit $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$, et on note $a \mid b$, s’il existe un entier relatif $k$ tel que $b = ka$. On dit aussi que $b$ est un multiple de $a$, ou que $a$ est un diviseur de $b$.

Exemples. $-6 \mid 42$ car $42 = (-7) \times (-6)$. Tout entier divise $0$ ($0 = 0 \times a$). $1$ et $-1$ divisent tout entier. Les diviseurs de $12$ dans $\mathbb{Z}$ sont $\pm 1$, $\pm 2$, $\pm 3$, $\pm 4$, $\pm 6$, $\pm 12$.

Propriétés. Soit $a$, $b$, $c$ des entiers relatifs.

1. Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
2. Combinaisons linéaires : si $a \mid b$ et $a \mid c$, alors pour tous entiers $u$ et $v$, $a \mid bu + cv$.
3. Si $a \mid b$ avec $b \neq 0$, alors $|a| \leqslant |b|$.

→ S’entraîner : Exercice 1 · Exercice 2

2. Division euclidienne

Théorème (division euclidienne). Soit $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$. Il existe un unique couple d’entiers $(q\,;\,r)$ tel que $$a = bq + r \qquad\text{et}\qquad 0 \leqslant r < b.$$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.

Exemples.

• $a = 100$, $b = 7$ : $100 = 7 \times 14 + 2$, quotient $14$, reste $2$.
• $a = -100$, $b = 7$ : $-100 = 7 \times (-15) + 5$, quotient $-15$, reste $5$ (et non $-2$ : un reste est toujours positif).

Conséquence. $b$ divise $a$ si et seulement si le reste de la division euclidienne de $a$ par $b$ est nul. Tout entier s’écrit sous l’une des formes $bk$, $bk + 1$, …, $bk + (b - 1)$ : c’est la base des disjonctions de cas.

Exemple. Tout entier $n$ s’écrit $3k$, $3k + 1$ ou $3k + 2$. Alors $n^2$ vaut $9k^2$, $9k^2 + 6k + 1$ ou $9k^2 + 12k + 4$ : le reste de $n^2$ dans la division par $3$ est toujours $0$ ou $1$, jamais $2$.

def division(a, b):
    """Quotient et reste de la division euclidienne de a par b > 0."""
    return a // b, a % b     # en Python, a % b est toujours dans [0 ; b[ si b > 0

print(division(100, 7))    # (14, 2)
print(division(-100, 7))   # (-15, 5)

→ S’entraîner : Exercice 3

3. Congruences

Définition. Soit $n \geqslant 2$ un entier. Deux entiers $a$ et $b$ sont congrus modulo $n$, et on note $a \equiv b\ [n]$, si $n$ divise $a - b$.

Propriété. $a \equiv b\ [n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. En particulier, si $r$ est le reste de la division de $a$ par $n$, alors $a \equiv r\ [n]$ avec $0 \leqslant r < n$.

Exemples. $38 \equiv 3\ [5]$ ; $-4 \equiv 8\ [12]$ (il est $8$ h quand on recule de $4$ h depuis midi) ; $n$ est pair si et seulement si $n \equiv 0\ [2]$.

Propriétés. Pour $n \geqslant 2$ : la congruence est réflexive ($a \equiv a$), symétrique et transitive (si $a \equiv b$ et $b \equiv c$ modulo $n$, alors $a \equiv c$).

→ S’entraîner : Exercice 4

4. Compatibilité avec les opérations

Théorème. Soit $n \geqslant 2$. Si $a \equiv b\ [n]$ et $c \equiv d\ [n]$, alors :

• $a + c \equiv b + d\ [n]$ et $a - c \equiv b - d\ [n]$ ;
• $ac \equiv bd\ [n]$ ;
• pour tout entier naturel $k$, $a^k \equiv b^k\ [n]$.

Attention. On ne peut pas diviser une congruence n’importe comment : $2 \times 3 \equiv 2 \times 0\ [6]$ mais $3 \not\equiv 0\ [6]$.

print(pow(7, 100, 5))   # 1 : pow(a, k, n) calcule a**k modulo n très rapidement

→ S’entraîner : Exercice 5 · Exercice 6

5. Critères de divisibilité et congruences à résoudre

Critères de divisibilité. Un entier $N = \overline{a_k \dots a_1 a_0} = a_k 10^k + \dots + a_1 10 + a_0$ :

• comme $10 \equiv 1\ [9]$, $10^j \equiv 1\ [9]$ donc $N \equiv a_k + \dots + a_1 + a_0\ [9]$ : $N$ et la somme de ses chiffres ont le même reste modulo 9 (et modulo 3) ;
• comme $10 \equiv -1\ [11]$, $N \equiv a_0 - a_1 + a_2 - \dots\ [11]$ : critère de divisibilité par $11$ (somme alternée des chiffres).

Exemple. $N = 918\,082$ : $2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0\ [11]$, donc $11 \mid N$.

Résoudre une congruence $ax \equiv b\ [n]$. Il suffit de tester les $n$ restes possibles de $x$ : c’est une table de congruences.

Exemple. Résoudre $3x \equiv 5\ [7]$.

$x \equiv$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3x \equiv$	$0$	$3$	$6$	$2$	$5$	$1$	$4$

Les solutions sont les entiers $x \equiv 4\ [7]$, c’est-à-dire $x = 4 + 7k$, $k \in \mathbb{Z}$.

On lit aussi dans la table que $3 \times 5 \equiv 1\ [7]$ : $5$ est un inverse de $3$ modulo $7$. Multiplier $3x \equiv 5$ par $5$ donne directement $x \equiv 25 \equiv 4\ [7]$.

Remarque. Un inverse de $a$ modulo $n$ n’existe pas toujours (il n’y a pas d’inverse de $2$ modulo $6$) : le chapitre suivant (PGCD, Bézout et Gauss) dira exactement quand.

→ S’entraîner : Exercice 7 · Exercice 8

À retenir.

• $a \mid b \iff b = ka$ ; si $a \mid b$ et $a \mid c$, alors $a \mid bu + cv$.
• Division euclidienne : $a = bq + r$ avec $0 \leqslant r < b$, unique.
• $a \equiv b\ [n] \iff n \mid a - b \iff$ même reste modulo $n$.
• Les congruences se conservent par $+$, $-$, $\times$ et puissance, pas par division.
• Chercher une puissance congrue à $\pm 1$ pour calculer des restes ; table de congruences pour résoudre $ax \equiv b\ [n]$.