Proth's theorem
From Wikipedia, the free encyclopedia
In mathematics, Proth's theorem in number theory 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, then if for some integer a,
then p is prime (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.
Contents |
[edit] Numerical examples
Examples of the theorem include:
- for p = 3, 21 + 1 = 3 is divisible by 3, so 3 is prime.
- for p = 5, 32 + 1 = 10 is divisible by 5, so 5 is prime.
- for p = 13, 56 + 1 = 15626 is divisible by 13, so 13 is prime.
- for p = 9, which is not prime, there is no a such that a4 + 1 is divisible by 9.
The first Proth primes are (sequence A080076 in OEIS):
As of 2007, the largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust. It has 3918990 digits and is the largest known prime which is not a Mersenne prime. [1]
[edit] History
François Proth (1852 - 1879) published the theorem around 1878.
[edit] See also
[edit] External links
|
|||||||||||||||||
