Proth's Theorem

created by General Wesc
(idea) by General Wesc (2 d) (print)   (I like it!) 1 C! Sat Nov 13 1999 at 10:04:16
A theorem by Francois Proth1 for finding primes:
Let N = k.2n+1 with 2n > k. If there is an integer a such that a(N-1)/2 = -1 (mod N),
then N is prime.

This test is so simple that the difficulty is quickly multiplying the large numbers involved. It (also?) applies to Cullen Primes, Fermat Factors, and the primes in the Sierpinski Conjecture.

1 Props to wertperch for finding me his first initial and auraseer for his first name.

Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.