Fermat Divisors

The Prime Pages

GIMPS has discovered a new largest known prime number: 2^82589933-1 (24,862,048 digits)

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 193 · 2^3329782 + 1 1002367 L3460 Jul 2014 Divides Fermat F(3329780)
2 57 · 2^2747499 + 1 827082 L3514 May 2013 Divides Fermat F(2747497)
3 267 · 2^2662090 + 1 801372 L3234 Feb 2015 Divides Fermat F(2662088)
4 9 · 2^2543551 + 1 765687 L1204 Jun 2011 Divides Fermat F(2543548), GF(2543549, 3), GF(2543549, 6), GF(2543549, 12)
5 3 · 2^2478785 + 1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
6 7 · 2^2167800 + 1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
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 25 · 2^2141884 + 1 644773 L1741 Sep 2011 Divides Fermat F(2141872), GF(2141871, 5), GF(2141872, 10); generalized Fermat
9 183 · 2^1747660 + 1 526101 L2163 Mar 2013 Divides Fermat F(1747656)
10 131 · 2^1494099 + 1 449771 L2959 Feb 2012 Divides Fermat F(1494096)
11 329 · 2^1246017 + 1 375092 L2085 Jan 2012 Divides Fermat F(1246013)
12 2145 · 2^1099064 + 1 330855 L1792 Jun 2013 Divides Fermat F(1099061)
13 11 · 2⁹⁶⁰⁹⁰¹ + 1 289262 g277 Feb 2005 Divides Fermat F(960897)
14 1705 · 2⁹⁰⁶¹¹⁰ + 1 272770 L3174 Jun 2012 Divides Fermat F(906108)
15 27 · 2⁶⁷²⁰⁰⁷ + 1 202296 g279 Aug 2005 Divides Fermat F(672005)
16 659 · 2⁶¹⁷⁸¹⁵ + 1 185984 L732 Apr 2009 Divides Fermat F(617813)
17 151 · 2⁵⁸⁵⁰⁴⁴ + 1 176118 L446 Mar 2007 Divides Fermat F(585042)
18 519 · 2⁵⁶⁷²³⁵ + 1 170758 L656 Mar 2009 Divides Fermat F(567233)
19 243 · 2⁴⁹⁵⁷³² + 1 149233 L165 May 2007 Divides Fermat F(495728), GF(495726, 3), GF(495728, 6), GF(495727, 12)
20 651 · 2⁴⁷⁶⁶³² + 1 143484 L668 Dec 2008 Divides Fermat F(476624)

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 193 · 2^3329782 + 1 1002367 L3460 Jul 2014 Divides Fermat F(3329780)
2 267 · 2^2662090 + 1 801372 L3234 Feb 2015 Divides Fermat F(2662088)
3 2145 · 2^1099064 + 1 330855 L1792 Jun 2013 Divides Fermat F(1099061)
4 57 · 2^2747499 + 1 827082 L3514 May 2013 Divides Fermat F(2747497)
5 1705 · 2⁹⁰⁶¹¹⁰ + 1 272770 L3174 Jun 2012 Divides Fermat F(906108)
6 183 · 2^1747660 + 1 526101 L2163 Mar 2013 Divides Fermat F(1747656)
7 329 · 2^1246017 + 1 375092 L2085 Jan 2012 Divides Fermat F(1246013)
8 131 · 2^1494099 + 1 449771 L2959 Feb 2012 Divides Fermat F(1494096)
9 25 · 2^2141884 + 1 644773 L1741 Sep 2011 Divides Fermat F(2141872), GF(2141871, 5), GF(2141872, 10); generalized Fermat
10 9 · 2^2543551 + 1 765687 L1204 Jun 2011 Divides Fermat F(2543548), GF(2543549, 3), GF(2543549, 6), GF(2543549, 12)
11 659 · 2⁶¹⁷⁸¹⁵ + 1 185984 L732 Apr 2009 Divides Fermat F(617813)
12 519 · 2⁵⁶⁷²³⁵ + 1 170758 L656 Mar 2009 Divides Fermat F(567233)
13 7 · 2^2167800 + 1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
14 651 · 2⁴⁷⁶⁶³² + 1 143484 L668 Dec 2008 Divides Fermat F(476624)
15 3 · 2^2478785 + 1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
16 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)
17 151 · 2⁵⁸⁵⁰⁴⁴ + 1 176118 L446 Mar 2007 Divides Fermat F(585042)
18 243 · 2⁴⁹⁵⁷³² + 1 149233 L165 May 2007 Divides Fermat F(495728), GF(495726, 3), GF(495728, 6), GF(495727, 12)
19 11 · 2⁹⁶⁰⁹⁰¹ + 1 289262 g277 Feb 2005 Divides Fermat F(960897)
20 27 · 2⁶⁷²⁰⁰⁷ + 1 202296 g279 Aug 2005 Divides Fermat F(672005)

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

References