查看“︁費馬數”︁的源代码

{{NoteTA
|G1 = Math
}}
{{unsolved|数学|当<math> n > 4 </math>时，是否每个费马数都是[[合数]]？(可能可以用數學歸納法證明)}}
'''費馬數'''是以数学家[[费马]]命名的一组[[自然数]]，具有形式：

:<math>F_{n} = 2^{2^n} + 1</math>

其中<math>n</math>为非负整数。

若<math>2^n+1</math>是[[素数]]，可以得到''n''必须是2的[[幂]]。（若<math>n=ab</math>，其中<math>1 < a, b < n</math>且''b''为奇数，则<math>2^n+1 \equiv (2^a)^b+1 \equiv (-1)^b+1 \equiv 0 \pmod{2^a+1}</math>，即<math>2^a+1</math>是<math>2^n+1</math>的因數。）也就是说，所有具有形式<math>2^n+1</math>的素数必然是費馬數，这些素数称为'''費馬素數'''。已知的費馬素數只有<math>F_0</math>至<math>F_4</math>五個。

==基本性质==

费马数满足以下的[[遞迴關係式|递归关系]]：

:<math>F_{n} = (F_{n-1}-1)^{2}+1\,</math>
:<math>F_{n} = F_{n-1} + 2^{2^{n-1}}F_{0} \cdots F_{n-2}</math>
:<math>F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2</math>
:<math>F_{n} = F_{0} \cdots F_{n-1} + 2</math>

其中<math>n\geqslant2</math>。这些等式都可以用[[数学归纳法]]推出。从最后一个等式中，我们可以推出哥德巴赫定理：任何两个费马数都没有大于1的[[公因子]]。要推出这个，我们需要假设<math>0 \leqslant i < j</math>且<math>F_i</math>和<math>F_j</math>有一个公因子<math>a > 1</math>。那么<math>a</math>能把

:<math>F_{0} \cdots F_{j-1}</math>

和''<math>F_j</math>''都整除；则''<math>a</math>''能整除它们相减的差。因为<math>a > 1</math>，这使得<math>a = 2</math>。造成矛盾。因为所有的费马数显然是奇数。作为一个推论，我们得到素数个数[[无穷]]的又一个证明。

其他性质：
*''<math>F_n</math>''的位数<math>D(n,b)</math>可以表示成以<math>b</math>为[[进位制|基数]]就是

:<math>D(n,b) = \left\lfloor \log_{b}\left(2^{2^{\overset{n}{}}}+1\right)+1 \right\rfloor \approx \lfloor 2^{n}\,\log_{b}2+1 \rfloor </math> (参见[[高斯函数]]).
*除了<math>F_1 = 2 + 3</math>以外没有费马数可以表示成两个[[素数]]的和。
*当<math>p</math>是奇素数的时候，没有费马数可以表示成两个数的''p''次方相减的形式。
*除了<math>F_0</math>和<math>F_1</math>，费马数的最后一位是7。
* 所有费马数{{OEIS|id=A051158}}的倒数之和是[[无理数]]。 ([[所羅門·格倫布|所罗门·格伦布]],1963)

==费马数的因式分解==
最小的12个費馬數为：

{|
|-
|''F''<sub>0</sub> ||=|| 2<sup>1</sup>||+||1 ||=||[[3]]||
|-
|''F''<sub>1</sub> ||=|| 2<sup>2</sup>||+||1 ||=||[[5]]||
|-
|''F''<sub>2</sub> ||=|| 2<sup>4</sup>||+||1 ||=||[[17]]||
|-
|''F''<sub>3</sub> ||=|| 2<sup>8</sup>||+||1 ||=||[[257]]||
|-
|''F''<sub>4</sub> ||=|| 2<sup>16</sup>||+||1 ||=||[[65537|65,537]] 以上5个是已知的费马素数。||
|-
|''F''<sub>5</sub> ||=|| 2<sup>32</sup>||+||1 ||=||4,294,967,297|| 
|- style="background:white; color:red"
| || || || || ||=||641 &times; 6,700,417
|-
|''F''<sub>6</sub> ||=|| 2<sup>64</sup>||+||1 ||=||18,446,744,073,709,551,617||
|- style="background:white; color:red"
| || || || || ||=||274,177 &times; 67,280,421,310,721
|-
|''F''<sub>7</sub> ||=|| 2<sup>128</sup>||+||1 ||=||340,282,366,920,938,463,463,374,607,431,768,211,457||
|- style="background:white; color:red"
| || || || || ||=||59,649,589,127,497,217 &times; 5,704,689,200,685,129,054,721
|-
|''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,639,937||
|- style="background:white; color:red"
| || || || || ||=||1,238,926,361,552,897 &times; 93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321
|-
|''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,030,073,546,<br>976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,097||
|- style="background:white; color:green; vertical-align:top"
| || || || || ||=|| 2,424,833 &times; 7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657 &times; 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519,023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737
|-
|''F''<sub>10</sub> ||=|| 2<sup>1024</sup>||+||1
||=||179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805,500,963,132,708,477,322,407,536,021,120,<br>113,879,871,393,357,658,789,768,814,416,622,492,847,430,639,474,124,377,767,893,424,865,485,276,302,219,601,246,094,119,453,082,952,085,<br>005,768,838,150,682,342,462,881,473,913,110,540,827,237,163,350,510,684,586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,217||
|- style="background:white; color:violet; vertical-align:top"
| || || || || ||=||                                                                                                         45,592,577 &times; 6,487,031,809 &times; 4,659,775,785,220,018,543,264,560,743,076,778,192,897 &times;
130,439,874,405,488,189,727,484,768,796,509,903,946,608,530,841,611,892,186,895,295,776,832,416,251,471,863,574,<br>140,227,977,573,104,895,898,783,928,842,923,844,831,149,032,913,798,729,088,601,617,946,094,119,449,010,595,906,<br>710,130,531,906,171,018,354,491,609,619,193,912,488,538,116,080,712,299,672,322,806,217,820,753,127,014,424,577
|-
|''F''<sub>11</sub> ||=|| 2<sup>2048</sup>||+||1
||=||32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,484,032,130,345,427,524,655,138,867,890,893,197,201,411,522,913,463,688,717,<br>960,921,898,019,494,119,559,150,490,921,095,088,152,386,448,283,120,630,877,367,300,996,091,750,197,750,389,652,106,796,057,638,384,067,<br>568,276,792,218,642,619,756,161,838,094,338,476,170,470,581,645,852,036,305,042,887,575,891,541,065,808,607,552,399,123,930,385,521,914,<br>333,389,668,342,420,684,974,786,564,569,494,856,176,035,326,322,058,077,805,659,331,026,192,708,460,314,150,258,592,864,177,116,725,943,<br>603,718,461,857,357,598,351,152,301,645,904,403,697,613,233,287,231,227,125,684,710,820,209,725,157,101,726,931,323,469,678,542,580,656,<br>697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,602,135,433,229,604,645,318,478,604,952,148,193,555,853,611,059,596,230,657||
|- style="background:white; color:blue; vertical-align:top"
| || || || || ||=|| 319,489 &times; 974,849 &times; 167,988,556,341,760,475,137 &times; 3,560,841,906,445,833,920,513 &times;
173,462,447,179,147,555,430,258,970,864,309,778,377,421,844,723,664,084,649,347,019,061,363,579,192,879,108,857,591,038,330,408,837,177,983,810,868,451,<br>546,421,940,712,978,306,134,189,864,280,826,014,542,758,708,589,243,873,685,563,973,118,948,869,399,158,545,506,611,147,420,216,132,557,017,260,564,139,<br>394,366,945,793,220,968,665,108,959,685,482,705,388,072,645,828,554,151,936,401,912,464,931,182,546,092,879,815,733,057,795,573,358,504,982,279,280,090,<br>942,872,567,591,518,912,118,622,751,714,319,229,788,100,979,251,036,035,496,917,279,912,663,527,358,783,236,647,193,154,777,091,427,745,377,038,294,<br>584,918,917,590,325,110,939,381,322,486,044,298,573,971,650,711,059,244,462,177,542,540,706,913,047,034,664,643,603,491,382,441,723,306,598,834,177
|-
|}
其中前八个来源于{{OEIS|id=A000215}}。

質因數個數顏色：
紅色：2個因數；綠色：3個因數；粉色：4個因數；藍色：5個因數；橘色：6個因數；紫色：7個因數(含以上)；

只有最小的12个費馬數被人们完全[[因数分解|分解]]了<ref>{{en icon}} [http://www.prothsearch.net/fermat.html 費馬數的分解] {{Wayback|url=http://www.prothsearch.net/fermat.html |date=20160210152415 }}</ref>，目前最小不確定質性的費馬數是<math>F_{33}</math>。

不確定質性的數：<math>F_n</math>，n = 33、34、35、44、45、46、...

== 历史 ==
1640年，[[费马]]提出了一个猜想，認為所有的费马数都是素数。这一猜想对最小的5个費馬數成立，于是费马宣称他找到了表示素数的公式。然而，[[欧拉]]在1732年否定了这一猜想，他给出了<math>F_5</math>的分解式：
:<math>F_5 = 2^{32} + 1 = 4294967297 = 641 \times 6700417</math> 

歐拉證明費馬數的因數皆可表成<math>k2^{n+1}+1</math>，之後[[爱德华·卢卡斯|卢卡斯]]證明費馬數的因數皆可表成<math>k2^{n+2}+1</math>。

費馬的本猜測到了大數可說是大錯特錯，甚至多數數學家認為不存在第6個費馬質數。

== 定理 ==
{{Main|可作图多边形}}
*[[卡爾·弗里德里希·高斯|高斯]]称：尺规作图[[正多边形]]的边数目的[[充分条件]]是2的非負整數次方乘以任意个（可为0个）不同的[[费马素数]]的积，解决了兩千年来悬而未决的难题。這個條件也是[[必要條件]]，但他沒有給出證明。

== 素性检验 ==

===方法一===
设<math>F_n=2^{2^n}+1</math>为第<math>n</math>个费马数。如果''<math>n</math>''不等于零，那么：

:<math>F_n</math>是素数，当且仅当<math>3^{\frac{F_n-1}{2}}\equiv-1\pmod{F_n}</math>。

===证明===

假设以下等式成立：
:<math>3^{\frac{F_n-1}{2}}\equiv-1\pmod{F_n}</math>
那么<math>3^{F_n-1}\equiv1\pmod{F_n}</math>，因此满足<math>3^k = 1 \pmod{F_n}</math>的最小整数<math>k</math>一定整除<math>F_n-1=2^{2^n}</math>，它是2的幂。另一方面，<math>k</math>不能整除<math>\tfrac{F_n-1}{2}</math>，因此它一定等于<math>F_n-1</math>。特别地，存在至少<math>F_n-1</math>个小于<math>F_n</math>且与<math>F_n</math>互素的数，这只能在<math>F_n</math>是素数时才能发生。

假设<math>F_n</math>是素数。根据[[欧拉准则]]，有：
:<math>3^{\frac{F_n-1}{2}}\equiv\left(\frac3{F_n}\right)\pmod{F_n}</math>,
其中<math>\left(\frac3{F_n}\right)</math>是[[勒让德符号]]。利用重复平方，我们可以发现<math>2^{2^n}\equiv1\pmod3</math>，因此<math>F_n\equiv2\pmod3</math>，以及<math>\left(\frac{F_n}3\right)=-1</math>。因为<math>F_n\equiv1\pmod4</math>，根据[[二次互反律]]，我们便可以得出结论<math>\left(\frac3{F_n}\right)=-1</math>。

===方法二===

根據[[費馬平方和定理]]，可證明某些費馬數為合數。(因為<math>4n+1</math>型的質數皆可表示為兩正整數的平方和，且表示方法唯一)
例如：
<math>F_5=(2^{16})^2+1^2=20449^2+62264^2</math>
<math>F_6=(2^{32})^2+1^2=1438793759^2+4046803256^2</math>

==注释==
<references />

{{皮埃爾·德·費馬}}

[[Category:整数数列|Fermat]]
[[Category:数学中未解决的问题]]
[[Category:大整数]]
[[Category:数学概念]]