费马数

费马数是以数学家费马命名的一组自然数，具有形式：

${\displaystyle F_{n}=2^{2^{n}}+1}$

其中${\displaystyle n}$为非负整数。

若${\displaystyle 2^{n}+1}$是素数，可以得到n必须是2的幂。（若${\displaystyle n=ab}$，其中${\displaystyle 1<a,b<n}$且b为奇数，则${\displaystyle 2^{n}+1\equiv (2^{a})^{b}+1\equiv (-1)^{b}+1\equiv 0{\pmod {2^{a}+1}}}$，即${\displaystyle 2^{a}+1}$是${\displaystyle 2^{n}+1}$的因数。）也就是说，所有具有形式${\displaystyle 2^{n}+1}$的素数必然是费马数，这些素数称为费马素数。已知的费马素数只有${\displaystyle F_{0}}$至${\displaystyle F_{4}}$五个。

基本性质

费马数满足以下的递归关系：

${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\,}$

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}}$

${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}}$

${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2}$

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

${\displaystyle F_{0}\cdots F_{j-1}}$

和${\displaystyle F_{j}}$都整除；则${\displaystyle a}$能整除它们相减的差。因为${\displaystyle a>1}$，这使得${\displaystyle a=2}$。造成矛盾。因为所有的费马数显然是奇数。作为一个推论，我们得到素数个数无穷的又一个证明。

其他性质：

• ${\displaystyle F_{n}}$的位数${\displaystyle D(n,b)}$可以表示成以${\displaystyle b}$为基数就是

${\displaystyle 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 }$ (参见高斯函数).

• 除了${\displaystyle F_{1}=2+3}$以外没有费马数可以表示成两个素数的和。
• 当${\displaystyle p}$是奇素数的时候，没有费马数可以表示成两个数的p次方相减的形式。
• 除了${\displaystyle F_{0}}$和${\displaystyle F_{1}}$，费马数的最后一位是7。
• 所有费马数（OEIS数列A051158）的倒数之和是无理数。 (所罗门·格伦布,1963)

费马数的因式分解

最小的12个费马数为：

F0	=	21	+	1	=	3
F1	=	22	+	1	=	5
F2	=	24	+	1	=	17
F3	=	28	+	1	=	257
F4	=	216	+	1	=	65,537 以上5个是已知的费马素数。
F5	=	232	+	1	=	4,294,967,297
					=	641 × 6,700,417
F6	=	264	+	1	=	18,446,744,073,709,551,617
					=	274,177 × 67,280,421,310,721
F7	=	2128	+	1	=	340,282,366,920,938,463,463,374,607,431,768,211,457
					=	59,649,589,127,497,217 × 5,704,689,200,685,129,054,721
F8	=	2256	+	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
					=	1,238,926,361,552,897 × 93,461,639,715,357,977,769,163,558,199,606,896,584,051,237,541,638,188,580,280,321
F9	=	2512	+	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, 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
					=	2,424,833 × 7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657 × 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
F10	=	21024	+	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, 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, 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
					=	45,592,577 × 6,487,031,809 × 4,659,775,785,220,018,543,264,560,743,076,778,192,897 × 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, 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, 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
F11	=	22048	+	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, 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, 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, 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, 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, 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
					=	319,489 × 974,849 × 167,988,556,341,760,475,137 × 3,560,841,906,445,833,920,513 × 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, 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, 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, 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, 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数列A000215）。

质因数个数颜色： 红色：2个因数；绿色：3个因数；粉色：4个因数；蓝色：5个因数；橘色：6个因数；紫色：7个因数(含以上)；

只有最小的12个费马数被人们完全分解了^[1]，目前最小不确定质性的费马数是${\displaystyle F_{33}}$。

不确定质性的数：${\displaystyle F_{n}}$，n = 33、34、35、44、45、46、...

历史

1640年，费马提出了一个猜想，认为所有的费马数都是素数。这一猜想对最小的5个费马数成立，于是费马宣称他找到了表示素数的公式。然而，欧拉在1732年否定了这一猜想，他给出了${\displaystyle F_{5}}$的分解式：

${\displaystyle F_{5}=2^{32}+1=4294967297=641\times 6700417}$

欧拉证明费马数的因数皆可表成${\displaystyle k2^{n+1}+1}$，之后卢卡斯证明费马数的因数皆可表成${\displaystyle k2^{n+2}+1}$。

费马的本猜测到了大数可说是大错特错，甚至多数数学家认为不存在第6个费马质数。

定理

主条目：可作图多边形

• 高斯称：尺规作图正多边形的边数目的充分条件是2的非负整数次方乘以任意个（可为0个）不同的费马素数的积，解决了两千年来悬而未决的难题。这个条件也是必要条件，但他没有给出证明。

素性检验

方法一

设${\displaystyle F_{n}=2^{2^{n}}+1}$为第${\displaystyle n}$个费马数。如果${\displaystyle n}$不等于零，那么：

${\displaystyle F_{n}}$是素数，当且仅当${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {F_{n}}}}$。

证明

假设以下等式成立：

${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {F_{n}}}}$

那么${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$，因此满足${\displaystyle 3^{k}=1{\pmod {F_{n}}}}$的最小整数${\displaystyle k}$一定整除${\displaystyle F_{n}-1=2^{2^{n}}}$，它是2的幂。另一方面，${\displaystyle k}$不能整除${\displaystyle {\tfrac {F_{n}-1}{2}}}$，因此它一定等于${\displaystyle F_{n}-1}$。特别地，存在至少${\displaystyle F_{n}-1}$个小于${\displaystyle F_{n}}$且与${\displaystyle F_{n}}$互素的数，这只能在${\displaystyle F_{n}}$是素数时才能发生。

假设${\displaystyle F_{n}}$是素数。根据欧拉准则，有：

${\displaystyle 3^{\frac {F_{n}-1}{2}}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$,

其中${\displaystyle \left({\frac {3}{F_{n}}}\right)}$是勒让德符号。利用重复平方，我们可以发现${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$，因此${\displaystyle F_{n}\equiv 2{\pmod {3}}}$，以及${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$。因为${\displaystyle F_{n}\equiv 1{\pmod {4}}}$，根据二次互反律，我们便可以得出结论${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$。

方法二

根据费马平方和定理，可证明某些费马数为合数。(因为${\displaystyle 4n+1}$型的质数皆可表示为两正整数的平方和，且表示方法唯一) 例如： ${\displaystyle F_{5}=(2^{16})^{2}+1^{2}=20449^{2}+62264^{2}}$ ${\displaystyle F_{6}=(2^{32})^{2}+1^{2}=1438793759^{2}[phone]^{2}}$

注释

1. （英文） 费马数的分解 （页面存档备份，存于互联网档案馆）