Petit théorème de Fermat~3 min
Soit $p$ un nombre premier.
• Si $a$ est un entier non divisible par $p$, alors $\boldsymbol{a^{p-1}\equiv1\ [p]}$.
• Pour tout entier $a$ : $\boldsymbol{a^{p}\equiv a\ [p]}$ (en multipliant par $a$ ; si $p\mid a$ les deux membres sont nuls modulo $p$).
Exemples : $2^{6}=64=9\times7+1\equiv1\ [7]$ ; $10^{12}\equiv1\ [13]$ ; pour tout $n$, $n^5\equiv n\ [5]$ ; avec $n^5\equiv n\ [2]$ (même parité) et $2\wedge5=1$, on obtient $n^5\equiv n\ [10]$ : $n^5$ a le même chiffre des unités que $n$.
Soit $p$ premier et $a$ non divisible par $p$ ; donc $a\wedge p=1$. Considérons les $p-1$ entiers $a,\ 2a,\ 3a,\ \dots,\ (p-1)a$.
(i) Aucun n'est divisible par $p$. Si $p\mid ka$ avec $1\leq k\leq p-1$, Gauss ($p\wedge a=1$) donne $p\mid k$, impossible car $0\lt k\lt p$.
(ii) Leurs restes modulo $p$ sont deux à deux distincts. Si $ia\equiv ja\ [p]$ avec $1\leq j\lt i\leq p-1$, alors $p\mid(i-j)a$ et, par Gauss, $p\mid i-j$ : impossible car $0\lt i-j\lt p$.
Les $p-1$ restes sont donc $p-1$ éléments distincts de $\{1,\dots,p-1\}$ : ce sont exactement $1,2,\dots,p-1$ dans un certain ordre. En multipliant les $p-1$ congruences $ka\equiv r_k$ : $$\begin{gathered}a\times2a\times\cdots\times(p-1)a\equiv1\times2\times\cdots\times(p-1)\ [p],\\ \text{soit}\quad a^{p-1}\,(p-1)!\equiv(p-1)!\ [p].\end{gathered}$$ Ainsi $p$ divise $(p-1)!\,(a^{p-1}-1)$. Or $p$ ne divise aucun des entiers $1,\dots,p-1$, donc $p\wedge(p-1)!=1$ (corollaire 3 de Gauss). Par Gauss, $p\mid a^{p-1}-1$ : $a^{p-1}\equiv1\ [p]$.
1. Vérifier $p\nmid a$ (sinon le reste est $0$). Alors $a^{p-1}\equiv1\ [p]$.
2. Diviser l'exposant : $k=(p-1)q+r$ avec $0\leq r\lt p-1$. Alors $a^k=(a^{p-1})^q\times a^r\equiv a^r\ [p]$.
3. Calculer $a^r$ modulo $p$ (en réduisant à chaque étape ; chercher une puissance plus petite congrue à $\pm1$ accélère).
Reste de $3^{2026}$ modulo $13$. $13$ premier et $13\nmid3$ : $3^{12}\equiv1\ [13]$. $2026=12\times168+10$, donc $3^{2026}=(3^{12})^{168}\times3^{10}\equiv3^{10}\ [13]$.
Or $3^3=27=2\times13+1\equiv1\ [13]$, donc $3^{10}=(3^3)^3\times3\equiv3\ [13]$. Le reste est $3$. (Contrôle : pow(3, 2026, 13) $=3$.)