# 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 the Fermat 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 fact that p=9 is not prime can be deterministically verified by checking that no such a (in mod 9) exists. This may be done by systematically checking each value of a from 2 to 8 (a=1 will never work). It is however sufficient to check values 2 to 5, or one-half of all possible values under 9. If 9 were a prime then by the pigeonhole principle, at lease one of these values of a will confirm primality, since it is expected that half of them would.
Alternatively, if we employ the deterministic variant wherein the quadratic nonresidual is directly computed, the work requires fewer iterations to confirm both compositeness and primality.
* for p = 97 = 3(2$^5$) + 1, we have a quadratic nonresidual of a=5, and that 5$^{(97-1)/2}$ + 1 = 3552713678800500929355621337890626 is divisible by 97, so 97 is prime.
* for p = 1537 = 3(2$^9$) + 1, we have a quadratic nonresidual of a=5, and that 5$^{(1537-1)/2}$ + 1 = 1052 (mod 1537) is not divisible by 1537, so 1537=29x53 is not prime.
In each of the previous two examples, an appropriate value of a was directly computed using a quadratic nonresidual computation such that the results of the test would be conclusive - a valid quadratic nonresidual in the prime case, and a candidate for one in the composite case. It was not necessarily to systematically search for an a to witness the prime case, or to reiterate the test a sufficient number of times for the composite.
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.