Proth prime

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.