Congruences : règles de calcul — MPSI

Pour calculer des restes de divisions, notamment de grandes puissances.

$a \equiv b\ [n]$ si $n \mid a - b$. Compatible avec $+$ et $\times$ : si $a \equiv b$ et $c \equiv d\ [n]$, alors $a + c \equiv b + d$ et $ac \equiv bd\ [n]$, d'où $a^k \equiv b^k\ [n]$.

Reste de $2^{100}$ modulo $7$ : $2^3 = 8 \equiv 1\ [7]$, $2^{100} = (2^3)^{33} \cdot 2$ ⇒ $2^{100} \equiv 2\ [7]$

On ne divise pas une congruence : $2a \equiv 2b\ [4]$ n'implique pas $a \equiv b\ [4]$.