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 k2n + 1 con k dispari e k < 2n, allora se per qualche numero intero a,
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.
Alcuni esempi di applicazione del teorema sono:
Alcuni tra i più piccoli numeri primi di Proth sono[1]:
Il più grande numero primo di Proth conosciuto è 10223 · 231172165 + 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. [1]
François Proth (1852 - 1879) elaborò il teorema nel 1878 circa.