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.
|Range of k||Ranges of n||Completed to|