Cours et exercices corrigés de terminale : Arithmétique dans Z et congruences

1. Division euclidienne et congruences

• Division euclidienne : Pour tout $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$, il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $a = bq + r$ avec $0 \le r < b$.
• Congruence : $a \equiv b \pmod{n} \iff n \mid (a - b) \iff a$ et $b$ ont le même reste dans la division euclidienne par $n$.

2. Propriétés opératoires des congruences

Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors :

• $a + c \equiv b + d \pmod{n}$
• $a \times c \equiv b \times d \pmod{n}$
• $a^k \equiv b^k \pmod{n}$ pour tout entier $k \ge 1$.

Démonstration : $(a + c) - (b + d) = (a - b) + (c - d)$ et $ac - bd = a(c - d) + d(a - b)$ ; comme $n$ divise $a - b$ et $c - d$, il divise ces combinaisons. La règle des puissances s'en déduit par récurrence sur $k$ (on multiplie $a^k \equiv b^k$ par $a \equiv b$).

3. Divisibilité dans $\mathbb{Z}$

• $a$ divise $b$ (noté $a \mid b$) s'il existe $k \in \mathbb{Z}$ tel que $b = ka$. Par exemple, $-4 \mid 12$ et tout entier divise $0$.
• Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
• Combinaisons linéaires : si $a \mid b$ et $a \mid c$, alors $a \mid bu + cv$ pour tous entiers $u$ et $v$.

Exemple : si $d$ divise $n + 3$ et $n + 1$, alors $d$ divise leur différence $2$, donc $d \in \{-2 ; -1 ; 1 ; 2\}$.

4. Critères de divisibilité et congruences

• Comme $10 \equiv 1 \pmod{9}$, on a $10^k \equiv 1 \pmod{9}$ pour tout $k$ : un entier est congru à la somme de ses chiffres modulo 9 (et modulo 3). D'où les critères de divisibilité par 3 et par 9.
• Comme $10 \equiv -1 \pmod{11}$, un entier est congru modulo 11 à la somme alternée de ses chiffres (en partant des unités). Exemple : $918\,082 \equiv 2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0 \pmod{11}$.
• En Python, le reste de $a$ par $n$ s'obtient avec $a \% n$, et $\text{pow}(a, k, n)$ calcule directement le reste de $a^k$ modulo $n$ : pow(3, 2024, 7) renvoie $2$.

5. Tables de congruences

Pour étudier une expression en $n$ modulo $m$, on remarque que $n$ est congru à l'un des restes $0, 1, \dots, m - 1$ : on dresse une table donnant la valeur de l'expression pour chaque reste.

• Exemple modulo 4 : $n^2 \equiv 0$ ou $1 \pmod{4}$ (restes $0, 1, 0, 1$ pour $n \equiv 0, 1, 2, 3$). Donc un carré n'est jamais congru à $2$ ou $3$ modulo $4$.
• Attention : on ne peut pas « simplifier » une congruence : $2x \equiv 2 \pmod{4}$ est vérifiée par $x = 3$, et pourtant $3 \not\equiv 1 \pmod{4}$.

6. Démonstration : existence et unicité de la division euclidienne

Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$.

• Existence : soit $q$ le plus grand entier tel que $bq \le a$ (c'est la partie entière de $\frac{a}{b}$). Alors $bq \le a < b(q + 1)$, et $r = a - bq$ vérifie $0 \le r < b$.
• Unicité : si $a = bq + r = bq' + r'$ avec $0 \le r < b$ et $0 \le r' < b$, alors $b(q - q') = r' - r$ avec $-b < r' - r < b$. Le seul multiple de $b$ strictement compris entre $-b$ et $b$ est $0$, donc $r = r'$, puis $q = q'$.

Exemple : pour $a = -17$ et $b = 5$, $5 \times (-4) = -20 \le -17 < -15$, donc $q = -4$ et $r = 3$ : $-17 = 5 \times (-4) + 3$.