Glossary:
Prime Pages:
Top 5000:

Though actually not a true class of primes, the primes of the form k^{.}2^{n}+1
with
2^{n} > k are often called the
Proth primes. They are named after the self taught farmer François
Proth who lived near Verdun, France (18521879). 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^{n}+1
with k odd and 2^{n} > k. Choose
an integer a so that the Jacobi symbol (a,N) is 1.
Then N is prime if and only if a^{(N1)/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^{n+2}+1. Cullen
primes have the form n^{.}2^{n}+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^{n}+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^{n}+1
(with no restriction on the relative sizes of n and k) to be a
Proth primebecause then every odd prime would be a Proth prime.
