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

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

then p is prime. This is a practical test because if p is prime, any chosen a has about a 50% chance of working.

Numerical examples

The first seven Proth numbers are (sequence A080075 in the OEIS):

P₀ = 2¹ + 1 = 3

P₁ = 2² + 1 = 5

P₂ = 2³ + 1 = 9

P₃ = 3 × 2² + 1 = 13

P₄ = 2⁴ + 1 = 17

P₅ = 3 × 2³ + 1 = 25

P₆ = 2⁵ + 1 = 33

Examples of the theorem include:

for p = 3, 2¹ plus 1 = 3 is divisible by 3, so 3 is prime.
for p = 5, 3² plus 1 = 10 is divisible by 5, so 5 is prime.
for p = 13, 5⁶ plus 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.

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