title: Teorema di Proth
text: # Teorema di Proth
  
  In teoria dei numeri, il teorema di Proth è un test di primalità per i numeri di Proth.
  
  Il teorema afferma che, se p è un numero di Proth, nella forma $k2^n$ + 1 con k dispari e k < $2^n,$ allora se per qualche numero intero a,
  
      $a^{(p-1)/2}\equiv -1{\pmod {p}}$
  
  allora p è primo (ed è chiamato primo di Proth). Questo test è pratico perché se p è primo, qualunque a arbitrariamente scelto ha circa il 50% di probabilità di funzionare.
  
  ## Esempi numerici
  
  Alcuni esempi di applicazione del teorema sono:
  
  * per p = 3, $2^1$ + 1 = 3 è divisibile per 3, dunque 3 è primo.
  * per p = 5, $3^2$ + 1 = 10 è divisibile per 5, dunque 5 è primo.
  * per p = 13, $5^6$ + 1 = 15626 è divisibile per 13, dunque 13 è primo.
  * per p = 9, che non è primo, non esiste alcun a tale che $a^4$ + 1 è divisibile per 9.
  
  Alcuni tra i più piccoli numeri primi di Proth sono:
  
      3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153
  
  Il più grande numero primo di Proth conosciuto è 10223 · $2^{31172165}$ + 1, trovato dal progetto di calcolo distribuito PrimeGrid. Ha 9.383.761 cifre ed è il più grande numero primo conosciuto a non essere un primo di Mersenne.
  
  ## Storia
  
  François Proth (1852 - 1879) elaborò il teorema nel 1878 circa.
  
  