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 ${\displaystyle F_{n}=2^{2^{n}}+1}$ è primo se e solo se

${\displaystyle 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

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

e

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

Per il criterio di Eulero, ${\displaystyle 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

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

Inversamente, se ${\displaystyle 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 ${\displaystyle 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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica