Proth's theorem


In number theory, Proth's theorem is a primality test for Proth numbers.
It states that if p is a Proth number, of the form k2n + 1 with k odd and k < 2n, and if there exists an integer a for which
then p is prime. In this case p is called a Proth prime. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working.
If a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until:
Thus, in contrast to many Monte Carlo primality tests, the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a running time that varies randomly.

Numerical examples

Examples of the theorem include:
The first Proth primes are :
The largest known Proth prime is, and is 9,383,761 digits long. It was found by Peter Szabolcs in the PrimeGrid distributed computing project which announced it on 6 November 2016. It is also the largest known non-Mersenne prime and largest Colbert number. The second largest known Proth prime is, found by Seventeen or Bust.

Proof

The proof for this theorem uses the Pocklington-Lehmer primality test, and closely resembles the proof of Pépin's test. The proof can be found on page 52 of the book by Ribenboim in the references.

History

published the theorem in 1878.