Proth

This page : Definition(s) | Records | References | Related Pages |

The Prime Pages

The Prime Pages keeps a list of the 5000 largest known primes, plus a few each of certain selected archivable forms and classes. These forms are defined in this collection's home page. This page is about one of those forms. Comments and suggestions requested.

Definitions and Notes

[To be written soon, for now:] In 1878 Francois Proth (a self-taught farmer) published a short note stating four theorems related to primes, including the on now known as Proth's theorem [Proth1878]:

Proth's Theorem : Let n = h^.2^k+1 with 2^k > h. If there is an integer a such that a^(n-1)/2 = -1 (mod n), then n is prime.

The Proth primes are those that meet the criteria of Proth's theorem.

Though Proth did not publish a proof, he did state in a letter that he had one (and Williams believes him [Williams98]). The earliest proof I have seen is by Robinson in the 1950's; but I find it hard to beleive that this is the first published proof since the proof is about two sentences long [Robinson57b]. Robinson [Robinson1958] listed the earlier tables: [Seelhoff1886, Cunningham1927, Kraitchik1924]; other early articles were [MW1977], [Shippee1978], and [Baillie1979].

Record Primes of this Type

rank prime digits who when comment

1 19249 · 2^13018586+1 3918990 SB10 May 2007
2 27653 · 2^9167433+1 2759677 SB8 Jun 2005
3 28433 · 2^7830457+1 2357207 SB7 Dec 2004
4 33661 · 2^7031232+1 2116617 SB11 Oct 2007
5 6679881 · 2^6679881+1 2010852 L917 Aug 2009 Cullen
6 1582137 · 2^6328550+1 1905090 L801 Apr 2009 Cullen
7 258317 · 2^5450519+1 1640776 g414 Jul 2008
8 3 · 2^5082306+1 1529928 L780 Apr 2009 Divides GF(5082303, 3), GF(5082305, 5)
9 5359 · 2^5054502+1 1521561 SB6 Dec 2003
10 265711 · 2^4858008+1 1462412 g414 Apr 2008
11 7 · 2^3511774+1 1057151 p236 Nov 2008 Divides GF(3511773, 6)
12 4847 · 2^3321063+1 999744 SB9 Oct 2005
13 7 · 2^3015762+1 907836 g279 Jan 2008
14 7 · 2^2915954+1 877791 g279 Jun 2008 Divides GF(2915953, 12) [g322]
15 222361 · 2^2854840+1 859398 g403 Sep 2006
16 3 · 2^2478785+1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
17 81 · 2^2468789+1 743182 g418 Sep 2009
18 3 · 2^2291610+1 689844 L753 Aug 2008 Divides GF(2291607, 3), GF(2291609, 5)
19 19 · 2^2206266+1 664154 p189 Sep 2006
20 7 · 2^2167800+1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)

Finding Primes and Proving Primality's n-1 tests

References

Baillie1979
R. Baillie, "New primes of the form k · 2ⁿ + 1," Math. Comp., 33:148 (October 1979) 1333--1336. MR 80h:10009 (Abstract available)
BCW81
Baillie, R., Cormack, G. and Williams, H.C., "The problem of Sierpinski concerning k · 2ⁿ + 1," Math. Comp., 37:155 (1981) 229--231. MR 83a:10006a [Corrigenda: [BCW1982]]
Chen2003
Chen, Yong-Gao, "On integers of the forms k^r-2ⁿ and k^r2ⁿ+1," J. Number Theory, 98:2 (2003) 310--319. MR1955419
Cunningham1927 (pp. 56-73)
A. J. C. Cunningham, Quadratic and linear tables, F. Hodgson, 1927.
HB1975
J. C. Hallyburton, Jr. and J. Brillhart, "Two new factors of Fermat numbers," Math. Comp., 29 (1975) 109--112. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR 51:5460
Kraitchik1924 (pp. 12-13)
M. Kraitchik, Recherches sur la th'eorie des nombres, W. W. Norton \& Co., Vol, 1, Gauthier-Vilars, 1924.
MW1977
G. Matthew and H. C. Williams, "Some new primes of the form k· 2ⁿ+1," Math. Comp., 31 (1977) 797--798. MR 55:12605
Proth1878
F. Proth, "Théorèmes sur les nombres premiers," C. R. Acad. Sci. Paris, 85 (1877) 329-331.
Robinson57b
R. M. Robinson, "The converse of Fermat's theorem," Amer. Math. Monthly, 64 (1957) 703--710. MR 20:4520
Robinson58
R. M. Robinson, "A report on primes of the form k· 2ⁿ + 1 and on factors of Fermat numbers," Proc. Amer. Math. Soc., 9 (1958) 673--681. MR 20:3097
Seelhoff1886
P. Seelhoff, "Die Zahlen von der Form k· 2ⁿ+1," Zeitschrift fur Mathematik und Physik, 31 (1886) 380.
Shippee1978
D. E. Shippee, "Four new factors of Fermat numbers," Math. Comp., 32:143 (1978) 941. (Abstract available)
Williams98 (pp. 121-140)
H. C. Williams, Édouard Lucas and primality testing, Canadian Math. Soc. Series of Monographs and Adv. Texts Vol, 22, John Wiley \& Sons, New York, NY, 1998. pp. x+525, ISBN 0-471-14852-0. MR 2000b:11139 (Annotation available)