The Prime Glossary: Proth prime

Proth prime
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

Though actually not a true class of primes, the primes of the form k^.2ⁿ+1 with 2ⁿ > k are often called the Proth primes. They are named after the self taught farmer François Proth who lived near Verdun, France (1852-1879). He stated four theorems (or tests) for primality (see [Williams98]). The one we are interested in is the following:

Proth's Theorem: Let N = k^.2ⁿ+1 with k odd and 2ⁿ > k. Choose an integer a so that the Jacobi symbol (a,N) is -1. Then N is prime if and only if a^(N-1)/2 -1 (mod N).

This form of prime often shows up upon mathematicians desks. For example, Euler showed that every divisor of the Fermat number F_n (n greater than 2) must have the form k^.2ⁿ⁺²+1. Cullen primes have the form n^.2ⁿ+1, so are a subset of the Proth primes, as are the Fermat primes (with k=1, n a power of 2). In the opposite direction, recall that a Sierpinski number is a positive, odd integer k for which the integers k^.2ⁿ+1 are composite for every positive integer n. So when seeking to settle the Sierpinski conjecture we look for a Proth prime for a fixed multiplier k.

Finally, notice that we do not define any prime of the form k^.2ⁿ+1 (with no restriction on the relative sizes of n and k) to be a Proth prime--because then every odd prime would be a Proth prime.