# Proth prime

Though actually not a true class of primes, the primes of the form k.2n+1 with 2n > 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.2n+1 with k odd and  2n > 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 Fn (n greater than 2) must have the form k.2n+2+1.  Cullen primes have the form n.2n+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.2n+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.2n+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.