# 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 k2$^n$ + 1 with k odd and k < 2$^n$, and if there exists an integer a for which
    $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},$
then p is prime. In this case p is called a Proth prime. Only one such value of a need be found for the test to deterministically confirm primality. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, and if p is not prime then no chosen a will work. Furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration.
As such we may form a Monte Carlo probabilistic test thus: if the test is repeatedly performed an m number of times, each iteration with a random a, each time failing to confirm primality, then we may infer that p is probably composite (contrary to the probably prime results typical of other Monte Carlo algorithms such as the Miller-Rabin test). An approximate upper bound error probability $\varepsilon <\left({\frac {1}{2}}\right)^{m}$ of a prime being falsely identified as composite can also be inferred. This probabilistic implementation is not typically performed, however.
In principle, since if p is prime, there is roughly a 50% chance of a chosen a of proving primality, we may form an inefficient deterministic test by checking about one-half of all possible a values smaller than n. Once more than n/2 distinct values of a have been tested, compositeness is deterministic. This variation of the test - akin to the deterministic variant of Fermat's primality test - is grossly inefficient and also never employed.
In practice, a quadratic nonresidue of p is found via a modified Euclid's algorithm and taken as the value of a, since if a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. For such an a the Legendre symbol is
       $\left({\frac {a}{p}}\right)=-1.$
Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive or false negative), this deterministic variant of the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a randomly varying runtime. Note that if a is chosen to be a quadratic nonresidue as described above, the runtime is constant, save for the time spent on finding such a quadratic nonresidue. Finding such a value is very fast compared to the actual test.

## Numerical examples

Examples of the theorem include:
* for p = 3 = 1(2$^1$) + 1, we have that 2$^{(3-1)/2}$ + 1 = 3 is divisible by 3, so 3 is prime.
* for p = 5 = 1(2$^2$) + 1, we have that 3$^{(5-1)/2}$ + 1 = 10 is divisible by 5, so 5 is prime.
* for p = 13 = 3(2$^2$) + 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 first Proth primes are (sequence A080076 in the OEIS):
    3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….
The largest known Proth prime as of 2016 is $10223\cdot 2^{31172165}+1$, and is 9,383,761 digits long. It was found by Peter Szabolcs in the PrimeGrid volunteer computing project which announced it on 6 November 2016. It is the 11-th largest known prime number as of January 2024, it was the largest known non-Mersenne prime until being surpassed in 2023, and is the largest Colbert number. The second largest known Proth prime is $202705\cdot 2^{21320516}+1$, found by PrimeGrid.

## 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

François Proth (1852–1879) published the theorem in 1878.