Congruences modulo $n$~3 min
Soit $n\geq2$. Deux entiers $a$ et $b$ sont congrus modulo $n$, noté $a\equiv b\ [n]$, si $n\mid(a-b)$, c.-à-d. si $a-b$ est un multiple de $n$.
Exemples : $17\equiv2\ [5]$, $-3\equiv4\ [7]$, $2026\equiv6\ [10]$ ; $a\equiv0\ [n]\iff n\mid a$.
• $a\equiv b\ [n]\iff a$ et $b$ ont le même reste dans la division euclidienne par $n$. En particulier, tout entier $a$ est congru modulo $n$ à un unique entier $r\in\{0,1,\dots,n-1\}$ : son reste.
(Si $a=nq+r$ et $b=nq'+r'$, alors $a-b=n(q-q')+(r-r')$ avec $|r-r'|\lt n$ ; donc $n\mid a-b\iff n\mid r-r'\iff r=r'$.)
• Réflexive ($a\equiv a$), symétrique ($a\equiv b\Rightarrow b\equiv a$), transitive ($a\equiv b$ et $b\equiv c\Rightarrow a\equiv c$).
Si $a\equiv b\ [n]$ et $c\equiv d\ [n]$, alors : $a+c\equiv b+d\ [n]$, $a-c\equiv b-d\ [n]$, $ac\equiv bd\ [n]$, et pour tout $k\in\mathbb{N}$ : $a^k\equiv b^k\ [n]$.
On peut donc remplacer chaque nombre par son reste (ou par un entier plus commode, comme $-1$) au fil d'un calcul.
Supposons $a\equiv b\ [n]$ et $c\equiv d\ [n]$ : il existe $k,l\in\mathbb{Z}$ tels que $a=b+kn$ et $c=d+ln$. Alors $$ac=(b+kn)(d+ln)=bd+bln+dkn+kln^2=bd+n\,(bl+dk+kln).$$ Donc $ac-bd$ est un multiple de $n$ : $ac\equiv bd\ [n]$.
Pour les puissances : en prenant $c=a$ et $d=b$, on obtient $a^2\equiv b^2$, puis par récurrence $a^k\equiv b^k$ (si $a^k\equiv b^k$, multiplier par $a\equiv b$).
Pour étudier une expression $f(n)$ modulo $m$, il suffit d'examiner les $m$ restes possibles de $n$ : on dresse un tableau des restes de $n$, puis de $f(n)$, en remplaçant chaque valeur par son reste au fur et à mesure.
Montrer que $n^2\equiv0$ ou $1\ [4]$.
Le carré d'un entier pair est $\equiv0$, celui d'un impair $\equiv1$ modulo $4$.
On ne divise pas : $2\times3\equiv2\times0\ [6]$ mais $3\not\equiv0\ [6]$ ; on ne « simplifie » un facteur qu'avec un inverse modulaire (partie 5). Les exposants ne se réduisent pas modulo $n$ : $2^4\not\equiv2^1\ [3]$ ; on réduit l'exposant avec la longueur du cycle (partie 4).