Prime Fermat Divisors

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

The Fermat primes are the primes of the form 2^2ⁿ+1 for non-negative integers n. Only five Fermat primes are known (n=0, 1, 2, 3, 4), and the Fermat numbers grow so quickly that it may be many years before the first undecided case: F₃₃ = 2^2^33+1

(a number with over 2.5 billion digits!) is shown prime or composite--unless we luck onto a divisor. So every since Euler found the first Fermat divisor (non-trivial divisor of a Fermat composite), factorers have been collecting these rare numbers.

Euler showed that that every divisor of F_n (n greater than 2) must have the form k^.2ⁿ⁺²+1 for some integer k. For this reason, when we find a large prime of the form k^.2ⁿ+1 (with k small), we usually check to see if it divides a Fermat number. (For example, Gallot's Win95 program Proth.exe has this test built in.)

Record Primes of this Type

rank prime digits who when comment

1 3 · 2^2478785+1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
2 7 · 2^2167800+1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
3 3 · 2^2145353+1 645817 g245 Feb 2003 Divides Fermat F(2145351), GF(2145351, 3), GF(2145352, 5), GF(2145348, 6), GF(2145352, 10), GF(2145351, 12)
4 11 · 2⁹⁶⁰⁹⁰¹+1 289262 g277 Feb 2005 Divides Fermat F(960897)
5 27 · 2⁶⁷²⁰⁰⁷+1 202296 g279 Aug 2005 Divides Fermat F(672005)
6 659 · 2⁶¹⁷⁸¹⁵+1 185984 L732 Apr 2009 Divides Fermat F(617813)
7 151 · 2⁵⁸⁵⁰⁴⁴+1 176118 L446 Mar 2007 Divides Fermat F(585042)
8 519 · 2⁵⁶⁷²³⁵+1 170758 L656 Mar 2009 Divides Fermat F(567233)
9 243 · 2⁴⁹⁵⁷³²+1 149233 L165 May 2007 Divides Fermat F(495728), GF(495726, 3), GF(495728, 6), GF(495727, 12)
10 651 · 2⁴⁷⁶⁶³²+1 143484 L668 Dec 2008 Divides Fermat F(476624)
11 89 · 2⁴⁷²⁰⁹⁹+1 142118 p114 Oct 2004 Divides Fermat F(472097)
12 9 · 2⁴⁶¹⁰⁸¹+1 138801 g122 Aug 2003 Divides Fermat F(461076), GF(461077, 3), GF(461077, 6), GF(461077, 12)
13 1207 · 2⁴¹⁰¹⁰⁸+1 123458 g380 Nov 2005 Divides Fermat F(410105)
14 3 · 2³⁸²⁴⁴⁹+1 115130 g132 Jul 1999 Divides Fermat F(382447), GF(382447, 3), GF(382447, 12), GF(382443, 6)
15 485 · 2³³⁸²⁹⁷+1 101841 L203 May 2007 Divides Fermat F(338295) [K]
16 3 · 2³⁰³⁰⁹³+1 91241 Y Jan 1998 Divides Fermat F(303088); GF(303088, 3), GF(303086, 6), GF(303092, 10), GF(303088, 12), GF(303092, 5) [g0]
17 211 · 2²⁸⁷³⁸⁸+1 86515 p43 Dec 2004 Divides Fermat F(287384)
18 51 · 2²⁸²⁷¹⁹+1 85109 g196 Nov 2002 Divides Fermat F(282717)
19 63 · 2²⁷⁰⁰⁹⁴+1 81309 gt Feb 2002 Divides Fermat F(270091)
20 3 · 2²¹³³²¹+1 64217 Y May 1997 Divides Fermat F(213319); GF(213319, 5), GF(213316, 6), GF(213319, 12) [g0]

Weighted Record Primes of this Type

For purposes of amusement only, we decided to try to rank these divisors based on the facts that (1) large primes are harder to find than small ones; and (2) the probability that N = k2ⁿ+1 divides a Fermat numbers appears to be O(1/k). (Note that all primes have this form!)

More specifically, the number of operations to prove N is prime is O(ln³N ln ln N). So to N = k2ⁿ+1 we might assign the weight

k ln³N ln ln N

To make these weights smaller we take the log this expression.

ln k + 3 ln ln N + ln ln ln N

Yves Gallot interprets this to suggest that if you want to find a Fermat factor, use a small n. If you want to find a record sized factor, use a small k.

rank prime digits who when comment

1 659 · 2⁶¹⁷⁸¹⁵+1 185984 L732 Apr 2009 Divides Fermat F(617813)
2 519 · 2⁵⁶⁷²³⁵+1 170758 L656 Mar 2009 Divides Fermat F(567233)
3 1207 · 2⁴¹⁰¹⁰⁸+1 123458 g380 Nov 2005 Divides Fermat F(410105)
4 7 · 2^2167800+1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
5 651 · 2⁴⁷⁶⁶³²+1 143484 L668 Dec 2008 Divides Fermat F(476624)
6 3 · 2^2478785+1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
7 3 · 2^2145353+1 645817 g245 Feb 2003 Divides Fermat F(2145351), GF(2145351, 3), GF(2145352, 5), GF(2145348, 6), GF(2145352, 10), GF(2145351, 12)
8 151 · 2⁵⁸⁵⁰⁴⁴+1 176118 L446 Mar 2007 Divides Fermat F(585042)
9 243 · 2⁴⁹⁵⁷³²+1 149233 L165 May 2007 Divides Fermat F(495728), GF(495726, 3), GF(495728, 6), GF(495727, 12)
10 485 · 2³³⁸²⁹⁷+1 101841 L203 May 2007 Divides Fermat F(338295) [K]
11 11 · 2⁹⁶⁰⁹⁰¹+1 289262 g277 Feb 2005 Divides Fermat F(960897)
12 89 · 2⁴⁷²⁰⁹⁹+1 142118 p114 Oct 2004 Divides Fermat F(472097)
13 27 · 2⁶⁷²⁰⁰⁷+1 202296 g279 Aug 2005 Divides Fermat F(672005)
14 211 · 2²⁸⁷³⁸⁸+1 86515 p43 Dec 2004 Divides Fermat F(287384)
15 63 · 2²⁷⁰⁰⁹⁴+1 81309 gt Feb 2002 Divides Fermat F(270091)
16 51 · 2²⁸²⁷¹⁹+1 85109 g196 Nov 2002 Divides Fermat F(282717)
17 9 · 2⁴⁶¹⁰⁸¹+1 138801 g122 Aug 2003 Divides Fermat F(461076), GF(461077, 3), GF(461077, 6), GF(461077, 12)
18 3 · 2³⁸²⁴⁴⁹+1 115130 g132 Jul 1999 Divides Fermat F(382447), GF(382447, 3), GF(382447, 12), GF(382443, 6)
19 3 · 2³⁰³⁰⁹³+1 91241 Y Jan 1998 Divides Fermat F(303088); GF(303088, 3), GF(303086, 6), GF(303092, 10), GF(303088, 12), GF(303092, 5) [g0]
20 3 · 2²¹³³²¹+1 64217 Y May 1997 Divides Fermat F(213319); GF(213319, 5), GF(213316, 6), GF(213319, 12) [g0]

Status of the factorization of Fermat numbers
The Prime Glossary's: Fermat divisor

References