Congruences — Terminale

Pour trouver le reste d'une grande puissance, démontrer un critère de divisibilité, résoudre $ax \equiv b$ $[n]$.

$a \equiv b$ $[n]$ ⇔ $n \mid a - b$ ⇔ $a$ et $b$ ont le même reste modulo $n$. Compatibilité : si $a \equiv b$ et $c \equiv d$ $[n]$, alors $a + c \equiv b + d$, $ac \equiv bd$, et $a^k \equiv b^k$ $[n]$.

1. Réduis la base modulo $n$.
2. Cherche une petite puissance congrue à 1 (ou à $\pm 1$).
3. Écris l'exposant par division euclidienne et conclus.

$2^3 = 8 \equiv 1$ $[7]$ ; $2^{100} = (2^3)^{33} \times 2 \equiv 2$ $[7]$ : reste 2.

On ne peut pas « diviser » une congruence en général : $2x \equiv 2$ $[4]$ n'implique pas $x \equiv 1$ $[4]$.