This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
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.
Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive), 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.
Examples of the theorem include:
- for p = 3 = 1(21) + 1, we have that 2(3-1)/2 + 1 = 3 is divisible by 3, so 3 is prime.
- for p = 5 = 1(22) + 1, we have that 3(5-1)/2 + 1 = 10 is divisible by 5, so 5 is prime.
- for p = 13 = 3(22) + 1, we have that 5(13-1)/2 + 1 = 15626 is divisible by 13, so 13 is prime.
- for p = 9, which is not prime, there is no a such that a(9-1)/2 + 1 is divisible by 9.
The largest known Proth prime as of 2016[update] is , and is 9,383,761 digits long. It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016. It is also the largest known non-Mersenne prime. The second largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust.
The proof for this theorem uses the Pocklington-Lehmer Primality Test, and closely resembles the proof of Pépin's test.