Mathématiques expertes (option) · Terminale · Arithmétique

Petit théorème de Fermat

• Si $p$ est premier et $a$ n'est pas multiple de $p$, alors $a^{p-1}\equiv 1 \pmod p$ ; pour tout entier $a$, on a aussi $a^p\equiv a \pmod p$.
• Démonstration : les restes de $a, 2a, \dots, (p-1)a$ sont les entiers $1, \dots, p-1$ dans un autre ordre ; on compare les produits et on simplifie avec le théorème de Gauss.
• Pour calculer $a^n$ modulo $p$, on réduit l'exposant $n$ modulo $p-1$ ; l'inverse de $a$ modulo $p$ est $a^{p-2}$.
• Si $a^{p-1}\not\equiv 1 \pmod p$ avec $a$ non multiple de $p$, alors $p$ n'est pas premier ; la réciproque n'est pas garantie.