Nombres premiers, petit théorème de Fermat — Terminale

Pour décomposer un entier, compter ses diviseurs, ou calculer $a^{n}$ modulo un nombre premier.

Un nombre premier a exactement deux diviseurs positifs (1 et lui-même). Tout entier $\geq 2$ se décompose de façon unique en produit de facteurs premiers. Il existe une infinité de nombres premiers. Fermat : si $p$ est premier et $p \nmid a$, alors $a^{p-1} \equiv 1$ $[p]$ ; pour tout $a$, $a^p \equiv a$ $[p]$.

1. Primalité : tester les diviseurs premiers $\leq \sqrt n$.
2. Décomposition : divisions successives par 2, 3, 5…
3. Fermat : réduis l'exposant modulo $p - 1$.

$360 = 2^3 \times 3^2 \times 5$ : $(3 + 1)(2 + 1)(1 + 1) = 24$ diviseurs. $3^{100}$ mod 7 : $3^6 \equiv 1$, $100 = 6 \times 16 + 4$, $3^4 = 81 \equiv 4$.

1 n'est pas premier ; Fermat exige $p$ premier et $p \nmid a$.