Proth primes: Definition and Status

Proth's Theorem (1878): 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. 

The test is simple, in practice the difficulty is multiplying the large numbers involved.  Yves Gallot has written a program for Windows95/NT4.0 which makes it easy! 

Primes of the form k.2n+1 are interesting as possible factors of Fermat numbers Fm = 2r + 1, where r = 2m is itself a power of two. Presently there are only about 250 such factors known (see the factoring status), so discovering a new one is a greater achievement. Gallot's program automatically makes the divisibility test for every prime found. But the primes have other mathematical applications, too.

In the past, numbers k.2n+1 have been tested for primality at wide areas of k and n. You can help to extend this search further by running Gallot's program. Below are links to tables of ranges of exponents n that still have to be tested for individual values of k. Each table shows which ranges of n are available for current testing, and which of them have been reserved or have already been tested for 3 < k < 300. Ranges above this are not included at this time since...

"It appears that the probability of each prime of the form k.2n+1 dividing a Fermat number is 1/k" (Harvey Dubner & Wilfrid Keller, "Factors of generalized Fermat numbers", Mathematics of Computation, Vol. 64, Number 209, January 1995, pp. 397-405).

For reserving a range, please return to the index page. Ranges of n should be reserved in blocks of 10,000, e.g., 30,000-40,000, except at the higher ranges of n where blocks of 5,000 or 2,000 can be selected as indicated in the tables. A contiguous row of such blocks can also be reserved, though it is suggested that a range be picked that can be completed in about a 2 month period of time.

Preference should be given to the lowest blocks available for a given k or even on an entire table. In any case, testing should be done so that the searcher can reliably report that the chosen range has been searched completely.

Primes k.2n+1
Range of k Ranges of n Completed to
3-7 450,000-2,640,000 450,000
9-31 268,000-2,000,000 270,000
33-99 200,000-500,000 200,000
101-199 150,000-320,000 150,000
201-299 150,000-300,000 150,000
301-399 130,000-270,000 130,000
401-499 130,000-280,000 130,000
501-599 200,000-320,000 200,000

Last Modified: 1 January, 2005