TOPICS
Search

Proth Prime


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.

A Sierpiński number of the second kind is a number k satisfying Sierpiński's composite number theorem, i.e., a Proth number k such that k·2^n+1 is composite for every n>=1.

The first few Proth primes are 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, ... (OEIS A080076).

The following table gives the first few indices n such that k·2^n+1 is prime for small k.

kOEISvalues of n for which k·2^n+1 is prime
11, 2, 4, 8, 16, ...
3A0022531, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, ...
5A0022541, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, ...
7A0323532, 4, 6, 14, 20, 26, 50, 52, 92, 120, ...
9A0022561, 2, 3, 6, 7, 11, 14, 17, 33, 42, 43, 63, ...

See also

Fermat Number, Payam Number, Pierpont Prime, Proth Number, Proth's Theorem, Sierpiński's Composite Number Theorem, Sierpiński Number of the Second Kind

Explore with Wolfram|Alpha

References

Ballinger, R. "Proth Search Page." http://www.prothsearch.net/.Caldwell, C. "Proth Prime." http://primes.utm.edu/glossary/page.php?sort=ProthPrime.Caldwell, C. K. "Yves Gallot's Proth.exe: An implementation of Proth's Theorem for Windows." http://www.utm.edu/research/primes/programs/gallot/.Keller, W. "The Least Prime of the Form k.2n+1 for Certain Values of k." Abstr. Amer. Math. Soc. 9, 417-418, 1988.McNamara, J. and Mills, M. "Factoring of Proth Numbers." http://www.fidn.org/proth1.html.Sloane, N. J. A. Sequences A002253/M1318, A002254/M2635, A002256/M0751, A032353, and A080076 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Proth Prime

Cite this as:

Weisstein, Eric W. "Proth Prime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ProthPrime.html

Subject classifications