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.