Utiliser le petit théorème de Fermat : méthode (Maths expertes)
Utiliser le petit théorème de Fermat
Pour calculer $a^k$ modulo un nombre premier $p$ qui ne divise pas $a$ :
- On vérifie que $p$ est premier et que $p \nmid a$.
- On écrit $a^{p-1} \equiv 1 \;[p]$.
- On divise $k$ par $p - 1$ : $k = (p-1)q + s$ avec $0 \leqslant s < p-1$.
- On conclut : $a^k \equiv a^s \;[p]$.
L'exposant $p-1$ fonctionne toujours, mais un exposant plus petit peut aussi convenir (par exemple $2^3 \equiv 1 \;[7]$).
n⁵ − n est divisible par 30
Soit $n \in \mathbb{Z}$.
- $5$ est premier, donc par le petit théorème de Fermat $n^5 \equiv n \;[5]$ : $5 \mid n^5 - n$.
- $n^5 - n = n(n^4 - 1) = n(n^2-1)(n^2+1) = (n-1)n(n+1)(n^2+1)$. Le produit $(n-1)n(n+1)$ de trois entiers consécutifs contient un multiple de $2$ et un multiple de $3$, donc $2 \mid n^5 - n$ et $3 \mid n^5 - n$.
- $2$ et $3$ sont premiers entre eux, donc $6 \mid n^5 - n$ (corollaire de Gauss). Puis $6$ et $5$ sont premiers entre eux, donc $30 \mid n^5 - n$.
La réciproque est fausse
Si $a^{n-1} \equiv 1 \;[n]$, on ne peut pas conclure que $n$ est premier.
Exemple : $2^{10} = 1024 = 3 \times 341 + 1$, donc $2^{10} \equiv 1 \;[341]$, puis $2^{340} = (2^{10})^{34} \equiv 1 \;[341]$. Pourtant $341 = 11 \times 31$ n'est pas premier.
En revanche, la contraposée est vraie et utile : si $a^{n-1} \not\equiv 1 \;[n]$ pour un $a$ premier avec $n$, alors $n$ n'est pas premier.
Inverse modulo un nombre premier
Si $p$ est premier et $p \nmid a$, alors $a \times a^{p-2} = a^{p-1} \equiv 1 \;[p]$ : $a^{p-2}$ est un inverse de $a$ modulo $p$. Par exemple, modulo $7$, un inverse de $3$ est $3^5 = 243 \equiv 5 \;[7]$, ce qui est cohérent avec $3 \times 5 = 15 \equiv 1 \;[7]$.