[go: up one dir, main page]

Fermat Divisors

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.

(up) Definitions and Notes

The Fermat primes are the primes of the form 22n+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: F33 = 2^2^33+1 (a number with over 2.5 billion digits!) is shown prime or composite--unless we luck onto a divisor.  So ever 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 Fn (n greater than 2) must have the form k.2n+2+1 for some integer k. For this reason, when we find a large prime of the form k.2n+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.)

(up) Record Primes of this Type

rankprime digitswhowhencomment
17 · 218233956 + 1 5488969 L4965 Oct 2020 Divides Fermat F(18233954)
227 · 27963247 + 1 2397178 L5161 Jan 2021 Divides Fermat F(7963245)
313 · 25523860 + 1 1662849 L1204 Jan 2020 Divides Fermat F(5523858)
4141 · 24192911 + 1 1262195 L5226 Jul 2023 Divides Fermat F(4192909)
5193 · 23329782 + 1 1002367 L3460 Jul 2014 Divides Fermat F(3329780)
657 · 22747499 + 1 827082 L3514 May 2013 Divides Fermat F(2747497)
7267 · 22662090 + 1 801372 L3234 Feb 2015 Divides Fermat F(2662088)
89 · 22543551 + 1 765687 L1204 Jun 2011 Divides Fermat F(2543548), GF(2543549, 3), GF(2543549, 6), GF(2543549, 12)
93 · 22478785 + 1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
107 · 22167800 + 1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
113 · 22145353 + 1 645817 g245 Feb 2003 Divides Fermat F(2145351), GF(2145351, 3), GF(2145352, 5), GF(2145348, 6), GF(2145352, 10), GF(2145351, 12)
1225 · 22141884 + 1 644773 L1741 Sep 2011 Divides Fermat F(2141872), GF(2141871, 5), GF(2141872, 10); generalized Fermat
13183 · 21747660 + 1 526101 L2163 Mar 2013 Divides Fermat F(1747656)
14131 · 21494099 + 1 449771 L2959 Feb 2012 Divides Fermat F(1494096)
15329 · 21246017 + 1 375092 L2085 Jan 2012 Divides Fermat F(1246013)
162145 · 21099064 + 1 330855 L1792 Jun 2013 Divides Fermat F(1099061)
1711 · 2960901 + 1 289262 g277 Feb 2005 Divides Fermat F(960897)
181705 · 2906110 + 1 272770 L3174 Jun 2012 Divides Fermat F(906108)
1913243 · 2699764 + 1 210655 L5808 Jul 2023 Divides Fermat F(699760)
2027 · 2672007 + 1 202296 g279 Aug 2005 Divides Fermat F(672005)

(up) 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 = k2n+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(ln3N ln ln N). So to N = k2n+1 we might assign the weight

k ln3N 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.

rankprime digitswhowhencomment
17 · 218233956 + 1 5488969 L4965 Oct 2020 Divides Fermat F(18233954)
227 · 27963247 + 1 2397178 L5161 Jan 2021 Divides Fermat F(7963245)
3141 · 24192911 + 1 1262195 L5226 Jul 2023 Divides Fermat F(4192909)
4193 · 23329782 + 1 1002367 L3460 Jul 2014 Divides Fermat F(3329780)
5267 · 22662090 + 1 801372 L3234 Feb 2015 Divides Fermat F(2662088)
613243 · 2699764 + 1 210655 L5808 Jul 2023 Divides Fermat F(699760)
72145 · 21099064 + 1 330855 L1792 Jun 2013 Divides Fermat F(1099061)
813 · 25523860 + 1 1662849 L1204 Jan 2020 Divides Fermat F(5523858)
957 · 22747499 + 1 827082 L3514 May 2013 Divides Fermat F(2747497)
101705 · 2906110 + 1 272770 L3174 Jun 2012 Divides Fermat F(906108)
11183 · 21747660 + 1 526101 L2163 Mar 2013 Divides Fermat F(1747656)
12329 · 21246017 + 1 375092 L2085 Jan 2012 Divides Fermat F(1246013)
13131 · 21494099 + 1 449771 L2959 Feb 2012 Divides Fermat F(1494096)
1425 · 22141884 + 1 644773 L1741 Sep 2011 Divides Fermat F(2141872), GF(2141871, 5), GF(2141872, 10); generalized Fermat
159 · 22543551 + 1 765687 L1204 Jun 2011 Divides Fermat F(2543548), GF(2543549, 3), GF(2543549, 6), GF(2543549, 12)
167 · 22167800 + 1 652574 g279 Apr 2007 Divides Fermat F(2167797), GF(2167799, 5), GF(2167799, 10)
173 · 22478785 + 1 746190 g245 Oct 2003 Divides Fermat F(2478782), GF(2478782, 3), GF(2478776, 6), GF(2478782, 12)
183 · 22145353 + 1 645817 g245 Feb 2003 Divides Fermat F(2145351), GF(2145351, 3), GF(2145352, 5), GF(2145348, 6), GF(2145352, 10), GF(2145351, 12)
1911 · 2960901 + 1 289262 g277 Feb 2005 Divides Fermat F(960897)
2027 · 2672007 + 1 202296 g279 Aug 2005 Divides Fermat F(672005)

(up) References

AB1986
Akushskii, I. Ya. and Burtsev, V. M., "Realization of primality tests for Mersenne and Fermat numbers," Vestnik Akad. Nauk Kazakh. SSR,:1 (1986) 52--59.  MR 843070
BLSTW88
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of bn ± 1, b=2,3,5,6,7,10,12 up to high powers, Amer. Math. Soc., 1988.  Providence RI, pp. xcvi+236, ISBN 0-8218-5078-4. MR 90d:11009 (Annotation available)
Brent1982
Brent, Richard P., "Succinct proofs of primality for the factors of some Fermat numbers," Math. Comp., 38:157 (1982) 253--255.  (http://dx.doi.org/10.2307/2007482) MR 637304
DK95
H. Dubner and W. Keller, "Factors of generalized Fermat numbers," Math. Comp., 64 (1995) 397--405.  MR 95c:11010
KLS2001
M. Krízek, F. Luca and L. Somer, 17 lectures on Fermat numbers: from number theory to geometry, CMS Books in Mathematics Vol, 9, Springer-Verlag, 2001.  New York, NY, pp. xvii + 257, ISBN 0-387-95332-9. MR 2002i:11001
McIntosh1983
McIntosh, Richard, "A necessary and sufficient condition for the primality of Fermat numbers," Amer. Math. Monthly, 90:2 (1983) 98--99.  (http://dx.doi.org/10.2307/2975806) MR 691180
Printed from the PrimePages <t5k.org> © Reginald McLean.