Proth's theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

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):

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 , 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]

Proof

The proof for this theorem uses the Pocklington-Lehmer Primality Test, and closely resembles the proof of Pépin's test.

History

François Proth (1852–1879) published the theorem around 1878.[citation needed]

See also

References

  1. ^ Chris Caldwell, The Top Twenty: Proth, from The Prime Pages.
  2. ^ "World Record Colbert Number discovered!". 
  3. ^ Chris Caldwell, The Top Twenty: Largest Known Primes, from The Prime Pages.
  4. ^ Caldwell, Chris K. "The Top Twenty: Largest Known Primes". 

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Proth%27s_theorem&oldid=797871867"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Proth's_theorem
This page is based on the copyrighted Wikipedia article "Proth's theorem"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA