費馬數

當$n > 4$時，是否每個費馬數都是合數？(可能可以用數學歸納法證明)

費馬數是以數學家費馬命名的一組自然數，具有形式：

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

其中$n$為非負整數。

若$2^n+1$是素數，可以得到 $n$ 必須是2的冪。（若$n=ab$，其中$1 < a, b < n$且b為奇數，則$2^n+1 \equiv (2^a)^b+1 \equiv (-1)^b+1 \equiv 0 \pmod{2^a+1}$，即$2^a+1$是$2^n+1$的因數。）也就是說，所有具有形式$2^n+1$的素數必然是費馬數，這些素數稱為費馬素數。已知的費馬素數只有$F_0$至$F_4$五個。

## 基本性質

費馬數滿足以下的遞歸關係：

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

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

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

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

其中$n\geqslant2$。這些等式都可以用數學歸納法推出。從最後一個等式中，我們可以推出哥德巴赫定理：任何兩個費馬數都沒有大於1的公因子。要推出這個，我們需要假設$0 \leqslant i < j$且$F_i$和$F_j$有一個公因子$a > 1$。那麼$a$能把

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

和$F_j$都整除；則$a$能整除它們相減的差。因為$a > 1$，這使得$a = 2$。造成矛盾。因為所有的費馬數顯然是奇數。作為一個推論，我們得到素數個數無窮的又一個證明。

其他性質：

- $F_n$的位數$D(n,b)$可以表示成以$b$為基數就是

$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$ (參見高斯函數).

- 除了$F_1 = 2 + 3$以外沒有費馬數可以表示成兩個素數的和。
- 當$p$是奇素數的時候，沒有費馬數可以表示成兩個數的 $p$ 次方相減的形式。
- 除了$F_0$和$F_1$，費馬數的最後一位是7。
- 大的費馬數除以小的費馬數的餘數都是2。
- 所有費馬數的倒數之和是無理數。(所羅門·格倫布,1963)

## 費馬數的因式分解

最小的12個費馬數為：

$F_0$｜=｜21｜+｜1｜=｜3

$F_1$｜=｜22｜+｜1｜=｜5

$F_2$｜=｜24｜+｜1｜=｜17

$F_3$｜=｜28｜+｜1｜=｜257

$F_4$｜=｜216｜+｜1｜=｜65,537 以上5個是已知的費馬素數。

$F_5$｜=｜232｜+｜1｜=｜4,294,967,297

=｜641 × 6,700,417

$F_6$｜=｜264｜+｜1｜=｜18,446,744,073,709,551,617

=｜274,177 × 67,280,421,310,721

$F_7$｜=｜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

$F_8$｜=｜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

$F_9$｜=｜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

$F_{10}$｜=｜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

$F_{11}$｜=｜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

其中前八個來源於。

質因數個數顏色：

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

只有最小的12個費馬數被人們完全分解了，目前最小不確定質性的費馬數是$F_{33}$。

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

## 歷史

1640年，費馬提出了一個猜想，認為所有的費馬數都是素數。這一猜想對最小的5個費馬數成立，於是費馬宣稱他找到了表示素數的公式。然而，歐拉在1732年否定了這一猜想，他給出了$F_5$的分解式：

$$F_5 = 2^{32} + 1 = 4294967297 = 641 \times 6700417$$

歐拉證明費馬數的因數皆可表成$k2^{n+1}+1$，之後盧卡斯證明費馬數的因數皆可表成$k2^{n+2}+1$。

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

## 定理

- 高斯稱：尺規作圖正多邊形的邊數目的充分條件是2的非負整數次方乘以任意個（可為0個）不同的費馬素數的積，解決了兩千年來懸而未決的難題。這個條件也是必要條件，但他沒有給出證明。

## 素性檢驗

### 方法一

設$F_n=2^{2^n}+1$為第$n$個費馬數。如果$n$不等於零，那麼：

$F_n$是素數，若且唯若$3^{\frac{F_n-1}{2}}\equiv-1\pmod{F_n}$。

### 證明

假設以下等式成立：

$$3^{\frac{F_n-1}{2}}\equiv-1\pmod{F_n}$$

那麼$3^{F_n-1}\equiv1\pmod{F_n}$，因此滿足$3^k = 1 \pmod{F_n}$的最小整數$k$一定整除$F_n-1=2^{2^n}$，它是2的冪。另一方面，$k$不能整除$\tfrac{F_n-1}{2}$，因此它一定等於$F_n-1$。特別地，存在至少$F_n-1$個小於$F_n$且與$F_n$互素的數，這只能在$F_n$是素數時才能發生。

假設$F_n$是素數。根據歐拉準則，有：

$3^{\frac{F_n-1}{2}}\equiv\left(\frac3{F_n}\right)\pmod{F_n}$,

其中$\left(\frac3{F_n}\right)$是勒讓德符號。利用重複平方，我們可以發現$2^{2^n}\equiv1\pmod3$，因此$F_n\equiv2\pmod3$，以及$\left(\frac{F_n}3\right)=-1$。因為$F_n\equiv1\pmod4$，根據二次互反律，我們便可以得出結論$\left(\frac3{F_n}\right)=-1$。

### 方法二

根據費馬平方和定理，可證明某些費馬數為合數。(因為$4n+1$型的質數皆可表示為兩正整數的平方和，且表示方法唯一)

例如：

$$F_5=(2^{16})^2+1^2=20449^2+62264^2$$ $$F_6=(2^{32})^2+1^2=1438793759^2+4046803256^2$$