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, 21 + 1 = 3 is divisible by 3, so 3 is prime.
- for p = 5, 32 + 1 = 10 is divisible by 5, so 5 is prime.
- for p = 13, 56 + 1 = 15626 is divisible by 13, so 13 is prime.
- for p = 9, which is not prime, there is no a such that a4 + 1 is divisible by 9.
François Proth (1852–1879) published the theorem around 1878.