Editing Fermat number (section)

==Factorization==
Because of Fermat numbers' size,  it is difficult to factorize or even to check primality. [[Pépin's test]] gives a necessary and sufficient condition for primality of Fermat numbers, and can be implemented by modern computers. The [[elliptic curve method]] is a fast method for finding small prime divisors of numbers. Distributed computing project ''Fermatsearch'' has found some factors of Fermat numbers. Yves Gallot's proth.exe has been used to find factors of large Fermat numbers. [[Édouard Lucas]], improving Euler's above-mentioned result, proved in 1878 that every factor of the Fermat number <math>F_n</math>, with ''n'' at least 2, is of the form <math>k\times2^{n+2}+1</math> (see [[Proth number]]), where ''k'' is a positive integer. By itself, this makes it easy to prove the primality of the known Fermat primes.

Factorizations of the first 12 Fermat numbers are:

:{|
|- valign="top"
|''F''<sub>0</sub> ||=|| 2<sup>1</sup>||+||1 ||=||[[3 (number)|3]] is prime||
|- valign="top"
|''F''<sub>1</sub> ||=|| 2<sup>2</sup>||+||1 ||=||[[5 (number)|5]] is prime||
|- valign="top"
|''F''<sub>2</sub> ||=|| 2<sup>4</sup>||+||1 ||=||[[17 (number)|17]] is prime||
|- valign="top"
|''F''<sub>3</sub> ||=|| 2<sup>8</sup>||+||1 ||=||[[257 (number)|257]] is prime||
|- valign="top"
|''F''<sub>4</sub> ||=|| 2<sup>16</sup>||+||1 ||=||[[65537 (number)|65,537]] is the largest known Fermat prime||
|- valign="top"
|''F''<sub>5</sub> ||=|| 2<sup>32</sup>||+||1 ||=||4,294,967,297||
|- style="background:transparent; color:#B00000"
| || || || || ||=||641 × 6,700,417 (fully factored 1732<ref>{{cite web |last1=Sandifer |first1=Ed |title=How Euler Did it |url=http://eulerarchive.maa.org/hedi/HEDI-2007-03.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://eulerarchive.maa.org/hedi/HEDI-2007-03.pdf |archive-date=2022-10-09 |url-status=live |website=MAA Online |publisher=Mathematical Association of America |access-date=2020-06-13}}</ref>)
|- valign="top"
|''F''<sub>6</sub> ||=|| 2<sup>64</sup>||+||1 ||=||18,446,744,073,709,551,617 (20 digits) ||
|- style="background:transparent; color:#B00000"
| || || || || ||=||274,177 × 67,280,421,310,721 (14 digits) (fully factored 1855)
|- valign="top"
|''F''<sub>7</sub> ||=|| 2<sup>128</sup>||+||1 ||=||340,282,366,920,938,463,463,374,607,431,768,211,457 (39 digits)||
|- style="background:transparent; color:#B00000"
| || || || || ||=||59,649,589,127,497,217 (17 digits) × 5,704,689,200,685,129,054,721 (22 digits) (fully factored 1970)
|- valign="top"
|''F''<sub>8</sub> ||=|| 2<sup>256</sup>||+||1 ||=||115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,<br>639,937 (78 digits)||
|- style="background:transparent; color:#B00000; vertical-align:top"
| || || || || ||=||1,238,926,361,552,897 (16 digits) × <br>93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321 (62 digits) (fully factored 1980)
|- valign="top"
|''F''<sub>9</sub> ||=|| 2<sup>512</sup>||+||1 ||=||13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,0<br>30,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6<br>49,006,084,097 (155 digits)||
|- style="background:transparent; color:#B00000; vertical-align:top"
| || || || || ||=|| 2,424,833 × 7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657 (49 digits) × <br>741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519,023,905,821,316,144,415,759,<br>504,705,008,092,818,711,693,940,737 (99 digits) (fully factored 1990)
|- valign="top"
|''F''<sub>10</sub> ||=|| 2<sup>1024</sup>||+||1
||=||179,769,313,486,231,590,772,930...304,835,356,329,624,224,137,217 (309 digits)||
|- style="background:transparent; color:#B00000; vertical-align:top"
| || || || || ||=||45,592,577 × 6,487,031,809 × 4,659,775,785,220,018,543,264,560,743,076,778,192,897 (40 digits) × <br>130,439,874,405,488,189,727,484...806,217,820,753,127,014,424,577 (252 digits) (fully factored 1995)
|- valign="top"
|''F''<sub>11</sub> ||=|| 2<sup>2048</sup>||+||1
||=||32,317,006,071,311,007,300,714,8...193,555,853,611,059,596,230,657 (617 digits)||
|- style="background:transparent; color:#B00000; vertical-align:top"
| || || || || ||=|| 319,489 × 974,849 × 167,988,556,341,760,475,137 (21 digits) × 3,560,841,906,445,833,920,513 (22 digits) × <br>173,462,447,179,147,555,430,258...491,382,441,723,306,598,834,177 (564 digits) (fully factored 1988)
|-
|}

{{As of|2023|4}}, only ''F''<sub>0</sub> to ''F''<sub>11</sub> have been completely [[integer factorization|factored]].<ref name="Keller"/> The [[distributed computing]] project Fermat Search is searching for new factors of Fermat numbers.<ref>{{cite web|url=http://www.fermatsearch.org/|title=:: F E R M A T S E A R C H . O R G :: Home page|website=www.fermatsearch.org|access-date=7 April 2018}}</ref> The set of all Fermat factors is [[OEIS:A050922|A050922]] (or, sorted, [[OEIS:A023394|A023394]]) in [[On-Line Encyclopedia of Integer Sequences|OEIS]].

The following factors of Fermat numbers were known before 1950 (since then, digital computers have helped find more factors):

{| class="wikitable"
|-
! Year
! Finder
! Fermat number
! Factor
|-
| 1732
| [[Euler]]
| <math>F_5</math>
| <math>5 \cdot 2^7 + 1</math>
|-
| 1732
| Euler
| <math>F_5</math> (fully factored)
| <math>52347 \cdot 2^7 + 1</math>
|-
| 1855
| [[Thomas Clausen (mathematician)|Clausen]]
| <math>F_6</math>
| <math>1071 \cdot 2^8 + 1</math>
|-
| 1855
| Clausen
| <math>F_6</math> (fully factored)
| <math>262814145745 \cdot 2^8 + 1</math>
|-
| 1877
| [[Ivan Pervushin|Pervushin]]
| <math>F_{12}</math>
| <math>7 \cdot 2^{14} + 1</math>
|-
| 1878
| Pervushin
| <math>F_{23}</math>
| <math>5 \cdot 2^{25} + 1</math>
|-
| 1886
| [[Paul Peter Heinrich Seelhoff|Seelhoff]]
| <math>F_{36}</math>
| <math>5 \cdot 2^{39} + 1</math>
|-
| 1899
| [[Allan Joseph Champneys Cunningham|Cunningham]]
| <math>F_{11}</math>
| <math>39 \cdot 2^{13} + 1</math>
|-
| 1899
| Cunningham
| <math>F_{11}</math>
| <math>119 \cdot 2^{13} + 1</math>
|-
| 1903
| [[Alfred Western|Western]]
| <math>F_9</math>
| <math>37 \cdot 2^{16} + 1</math>
|-
| 1903
| Western
| <math>F_{12}</math>
| <math>397 \cdot 2^{16} + 1</math>
|-
| 1903
| Western
| <math>F_{12}</math>
| <math>973 \cdot 2^{16} + 1</math>
|-
| 1903
| Western
| <math>F_{18}</math>
| <math>13 \cdot 2^{20} + 1</math>
|-
| 1903
| [[James Cullen (mathematician)|Cullen]]
| <math>F_{38}</math>
| <math>3 \cdot 2^{41} + 1</math>
|-
| 1906
| [[James C. Morehead|Morehead]]
| <math>F_{73}</math>
| <math>5 \cdot 2^{75} + 1</math>
|-
| 1925
| [[Maurice Kraitchik|Kraitchik]]
| <math>F_{15}</math>
| <math>579 \cdot 2^{21} + 1</math>
|-
|}

{{As of|2024|12}}, 371 prime factors of Fermat numbers are known, and 324 Fermat numbers are known to be composite.<ref name="Keller">{{Citation |first=Wilfrid |last=Keller |url=http://www.prothsearch.com/fermat.html#Summary |title=Prime Factors of Fermat Numbers |work=ProthSearch.com |date=January 18, 2021|access-date=January 19, 2021}}</ref> Several new Fermat factors are found each year.<ref>{{cite web |url=http://www.fermatsearch.org/news.html |title=::FERMATSEARCH.ORG:: News |website=www.fermatsearch.org |access-date=7 April 2018 }}</ref>