Proth's theorem
In number theory, Proth's theorem is a primality test for Proth numbers.
It states[1][2] 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, furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration.
In practice, however, a quadratic nonresidue of p is found via a modified Euclid's algorithm[citation needed] 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
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. 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
[edit]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 first Proth primes are (sequence A080076 in the OEIS):
The largest known Proth prime as of 2016[update] is , and is 9,383,761 digits long.[3] It was found by Peter Szabolcs in the PrimeGrid volunteer computing project which announced it on 6 November 2016.[4] 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,[5] and is the largest Colbert number.[citation needed] The second largest known Proth prime is , found by PrimeGrid.[6]
Proof
[edit]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
[edit]François Proth (1852–1879) published the theorem in 1878.[7][8]
See also
[edit]- Pépin's test (the special case k = 1, where one chooses a = 3)
- Sierpinski number
References
[edit]- ^ Paulo Ribenboim (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 52. ISBN 0-387-94457-5.
- ^ Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization (2 ed.). Boston, MA: Birkhauser. p. 104. ISBN 3-7643-3743-5.
- ^ Chris Caldwell, The Top Twenty: Proth, from The Prime Pages.
- ^ "World Record Colbert Number discovered!".
- ^ Chris Caldwell, The Top Twenty: Largest Known Primes, from The Prime Pages.
- ^ Caldwell, Chris K. "The Top Twenty: Largest Known Primes".
- ^ François Proth (1878). "Theoremes sur les nombres premiers". Comptes rendus de l'Académie des Sciences de Paris. 87: 926.
- ^ Leonard Eugene Dickson (1966). History of the Theory of Numbers. Vol. 1. New York, NY: Chelsea. p. 92.