Proth primeThough 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).
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.
Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.