# Proth prime

Though actually not a true class of primes, the primes of the form*k*

^{.}2

*+1 with 2*

^{n}*>*

^{n}*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^{n}*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*^{(N-1)/2}≡ -1 (mod*N*).

_{n}(

*n*greater than 2) must have the form

*k*

^{.}2

^{n+2}+1. Cullen primes have the form

*n*

^{.}2

*+1, so are a subset of the Proth primes, as are the Fermat primes (with*

^{n}*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 prime--because then every odd prime would be a Proth prime.

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.