Proth's theorem

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 "k"2^"n" + 1 with "k" odd and "k" < 2^"n", then if for some integer "a",

:$$a^{(p-1)/2}equiv -1 pmod{p},!

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.

Numerical examples

Examples of the theorem include:

* for "p" = 3, 2¹ + 1 = 3 is divisible by 3, so 3 is prime.
* for "p" = 5, 3² + 1 = 10 is divisible by 5, so 5 is prime.
* for "p" = 13, 5⁶ + 1 = 15626 is divisible by 13, so 13 is prime.
* for "p" = 9, which is not prime, there is no "a" such that "a"⁴ + 1 is divisible by 9.

The first Proth primes are OEIS|id=A080076::3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153

As of 2007, the largest known Proth prime is 19249 · 2^13018586 + 1, found by Seventeen or Bust. It has 3918990 digits and is the largest known prime which is not a Mersenne prime. [http://primes.utm.edu/top20/page.php?id=3]

History

François Proth (1852 - 1879) published the theorem around 1878.

ee also

*Sierpinski number

External links

*MathWorld|urlname=ProthsTheorem|title=Proth's Theorem