Congruences dans Z
Cours
1. Définition
Soit $n \in \mathbb{N}^*$. On dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \ [n]$, si $n$ divise $a-b$ (c'est-à-dire si $a$ et $b$ ont le même reste dans la division euclidienne par $n$).
2. Propriétés
La relation de congruence est réflexive, symétrique et transitive. Elle est surtout compatible avec les opérations : si $a \equiv b \ [n]$ et $c \equiv d \ [n]$, alors :
$$a+c \equiv b+d \ [n], \qquad a-c \equiv b-d \ [n], \qquad ac \equiv bd \ [n]$$
Et pour tout entier naturel $k$ : $a^k \equiv b^k \ [n]$.
3. Calculer un reste à l'aide des congruences
Pour déterminer le reste de $a^k$ modulo $n$, on cherche un petit exposant $p$ tel que $a^p \equiv 1 \ [n]$ (ou une valeur simple), puis on réduit $k$ modulo $p$.
Exemple
Chiffre des unités de $7^{100}$ : $7^1 \equiv 7$, $7^2 \equiv 9$, $7^3 \equiv 3$, $7^4 \equiv 1 \ [10]$ (cycle de longueur 4). Comme $100 = 4 \times 25$, $7^{100} \equiv 7^4 \equiv 1 \ [10]$ : le chiffre des unités est $1$.
4. Résoudre une équation de congruence
Pour résoudre $ax \equiv b \ [n]$, on peut tester les valeurs de $x$ entre $0$ et $n-1$, ou chercher un inverse de $a$ modulo $n$.
5. Applications
Les congruences permettent de retrouver les critères de divisibilité : comme $10 \equiv 1 \ [9]$, on a $10^k \equiv 1 \ [9]$ pour tout $k$, donc un nombre est congru à la somme de ses chiffres modulo $9$.