A Proth number that is prime, i.e., a number of the form N = k·2^n + 1 for odd k, n a positive integer, and 2^n>k. Factors of Fermat numbers are of this form as long as they satisfy the condition k odd and k<2^n. For example, the factor 6700417 = 1 + 52347·2^7 of F_5 is not a Proth prime since 52347>2^7. (Otherwise, every odd prime would be a Proth prime.) Proth primes satisfy Proth's theorem, i.e., a number N of this form is prime iff there exists a number a such that a^((N - 1)/2) is congruent to -1 modulo N. This provides an easy computational test for Proth primes. Yves Gallot has written a downloadable program for testing Proth primes and many of the largest currently known primes have been found with this program.

Fermat number | Payam number | Pierpont prime | Proth number | Proth's theorem | Sierpiński number of the second kind | Sierpiński's composite number theorem