Proth's theorem

Proth's theorem states that if p is a prime proth number ( of the form k * 2^n + 1 with k odd and k < 2^n ), then for some integer a,

$a^{q}\equiv -1{\pmod {p}}\,\!$

Where q = ( ( p-1)/2)

This means that if you can find some number a, that multiplied it by itself (p-1)/2 times and add 1, then if the result is divisible by p (see modular arithmetic), then the number is a prime.

Numerical examples

Examples of the theorem include ( all p are proth numbers):

• 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
• for p = 9, there is no a such that a^4 + 1 is divisible by 9, so 9 is not prime.

History

Francois Proth found the theorem around 1878.