Petit théorème de Fermat : énoncé (Maths expertes)
Petit théorème de Fermat
Soit $p$ un nombre premier et $a$ un entier relatif.
- $a^p \equiv a \;[p]$.
- Si de plus $p$ ne divise pas $a$, alors $a^{p-1} \equiv 1 \;[p]$.
Démonstration : Petit théorème de Fermat
Preuve
Point 1 pour $a \in \mathbb{N}$, par récurrence sur $a$.
- Pour $a = 0$ : $0^p = 0$.
- Supposons $a^p \equiv a \;[p]$. Par la formule du binôme : $$(a + 1)^p = a^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k + 1.$$ D'après le lemme, chaque terme de la somme est divisible par $p$. Donc $(a+1)^p \equiv a^p + 1 \equiv a + 1 \;[p]$ par hypothèse de récurrence.
Point 1 pour $a \in \mathbb{Z}$. Soit $r$ le reste de la division de $a$ par $p$ : $a \equiv r \;[p]$ avec $r \in \mathbb{N}$. Alors $a^p \equiv r^p \equiv r \equiv a \;[p]$.
Point 2. D'après le point 1, $p$ divise $a^p - a = a(a^{p-1} - 1)$. Comme $p$ est premier et ne divise pas $a$, le lemme d'Euclide donne $p \mid a^{p-1} - 1$, c'est-à-dire $a^{p-1} \equiv 1 \;[p]$.
Reste de 3^100 modulo 7
$7$ est premier et ne divise pas $3$, donc $3^6 \equiv 1 \;[7]$ (on peut vérifier : $3^6 = 729 = 7 \times 104 + 1$).
$100 = 6 \times 16 + 4$, donc $3^{100} = (3^6)^{16} \times 3^4 \equiv 3^4 = 81 \;[7]$. Or $81 = 7 \times 11 + 4$.
Le reste de $3^{100}$ dans la division par $7$ est $4$.