Test di Pépin
# Test di Pépin

In matematica, il test di Pépin è un test di primalità che può essere usato per stabilire se un numero di Fermat è primo oppure composto.

Fu sviluppato dal matematico francese Théophile Pépin (1826-1904).

Secondo tale test il numero $F_{n}=2^{2^{n}}+1$ è primo se e solo se

    $3^{\frac {F_{n}-1}{2}}\equiv -1\mod F_{n}$

Essendo l'esponente a sinistra una potenza di 2, l'espressione può essere valutata in modo relativamente rapido elevando ripetutamente al quadrato 3, con un algoritmo a tempo polinomiale; tuttavia, a causa della grandezza dei numeri $F_n,$ il test può essere usato soltanto per valori non troppo grandi di n.

## Dimostrazione

Per ogni $F_n,$ si ha sicuramente

    $F_{n}\equiv 1\mod 4$

e

    $F_{n}\equiv 2\mod 3$

Per il criterio di Eulero, $3^{\frac {F_{n}-1}{2}}\equiv \left({\frac {3}{F_{n}}}\right)\mod F_{n}$, dove si è usato il simbolo di Legendre; se $F_n$ è primo si può applicare la legge di reciprocità quadratica, e quindi

    $\left({\frac {3}{F_{n}}}\right)=\left({\frac {F_{n}}{3}}\right)=\left({\frac {2}{3}}\right)=-1$ .

Inversamente, se $3^{\frac {F_{n}-1}{2}}\equiv -1\mod F_{n}$, la stessa congruenza deve valere per ogni fattore primo p di $F_n;$ quindi si ha $3^{F_{n}-1}\equiv 1\mod p$, ovvero l'ordine di 3 modulo p divide $F_n-1,$ ed è quindi una potenza di 2. Ma tale ordine non divide $(F_n-1)/2$ (che è ancora una potenza di 2) e quindi deve essere precisamente $F_n-1.$ Quindi $p>F_n-1,$ e p deve essere precisamente $F_n,$ ovvero quest'ultimo è primo.

