**Proth's Theorem** (1878): Let *N = k*.2^{n}*+*1
with 2^{n}* > 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!

- Download Program from Chris K. Caldwell's Prime Site.
**Links to tables of ranges**

Primes of the form *k*.2^{n}+1 are
interesting as possible factors of **Fermat numbers** *F*_{m}
= 2^{r} + 1, where *r* = 2^{m}
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*.2^{n}+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.2^{n}+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.2^{n}+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 |

URL: http://www.prothsearch.net/status.html

Last Modified: 1 January, 2005