title: Test di Pépin
text: # 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.
  
  