Proth's theorem
 |
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)
|
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 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.
If a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until:
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.
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.[1] It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016.[2] It is also the largest known non-Mersenne prime.[3] The second largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust.[4]
History[edit]
François Proth (1852–1879) published the theorem around 1878.[citation needed]
See also[edit]
- Pépin's test (the special case k = 1, where one chooses a = 3)
- Sierpinski number
References[edit]
- ^ 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".
