Congruences et théorème de Fermat

Solution

1. Petit théorème de Fermat :
   Considérons l'ensemble $\{a, 2a, 3a, \ldots, (p-1)a\}$ modulo $p$.
   Ces $p-1$ résidus sont tous distincts et non nuls (car $p mid a$ et $p$ premier).
   Donc $\{a, 2a, \ldots, (p-1)a\} \equiv \{1, 2, \ldots, p-1\} \pmod{p}$.
   En multipliant : $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$.
   Comme $\gcd((p-1)!, p) = 1$, on divise : $a^{p-1} \equiv 1 \pmod{p}$.
2. $7^{100} \pmod{11}$ :
   Par Fermat, $7^{10} \equiv 1 \pmod{11}$.
   $100 = 10 \times 10$, donc $7^{100} = (7^{10})^{10} \equiv 1^{10} = 1 \pmod{11}$.
3. $30 | n^5 - n$ :
   $n^5 - n = n(n^4-1) = n(n-1)(n+1)(n^2+1)$.
   — Divisibilité par 2 : $n(n-1)$ contient deux entiers consécutifs.
   — Divisibilité par 3 : Parmi $n-1, n, n+1$, l'un est divisible par 3.
   — Divisibilité par 5 : Par Fermat, $n^5 \equiv n \pmod{5}$ pour tout $n$.
   Donc $2 \times 3 \times 5 = 30 | n^5 - n$.