Test di Pépin

Template:F 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 -1mod{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 1mod4$

e

$F_n\equiv 2mod3$

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 -1mod{F}_n$, la stessa congruenza deve valere per ogni fattore primo p di F_n; quindi si ha $3^{F_n-1}\equiv 1modp$, 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.