Proth Prime

A Proth number that is prime, i.e., a number of the form  for odd ,  a positive integer, and . Factors of Fermat numbers are of this form as long as they satisfy the condition  odd and . For example, the factor  of  is not a Proth prime since . (Otherwise, every odd prime would be a Proth prime.)

Proth primes satisfy Proth's theorem, i.e., a number  of this form is prime iff there exists a number a such that  is congruent to  modulo . 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  satisfying Sierpiński's composite number theorem, i.e., a Proth number  such that  is composite for every .

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  such that  is prime for small .

	OEIS	values of  for which  is prime
1		1, 2, 4, 8, 16, ...
3	A002253	1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, ...
5	A002254	1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, ...
7	A032353	2, 4, 6, 14, 20, 26, 50, 52, 92, 120, ...
9	A002256	1, 2, 3, 6, 7, 11, 14, 17, 33, 42, 43, 63, ...

REFERENCES:

Ballinger, R. "Proth Search Page." https://www.prothsearch.net/.

Caldwell, C. "Proth Prime." https://primes.utm.edu/glossary/page.php?sort=ProthPrime.

Caldwell, C. K. "Yves Gallot's Proth.exe: An implementation of Proth's Theorem for Windows." https://www.utm.edu/research/primes/programs/gallot/.

Keller, W. "The Least Prime of the Form  for Certain Values of ." Abstr. Amer. Math. Soc. 9, 417-418, 1988.

McNamara, J. and Mills, M. "Factoring of Proth Numbers." https://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."