睇費馬數嘅原碼

{{unCantonese}}
'''費馬數'''系以數學家[[費馬]]命名一組[[自然數]]，具有形式：

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

其中''n''為非負整數。

若2<sup>''n''</sup> + 1系[[素數]]，可以得到''n''必須系2嘅[[冪]]。（若''n'' = ''ab''，其中1 < ''a'', ''b'' < ''n''且''b''为奇数，则2<sup>''n''</sup> + 1 ≡ (2<sup>''a''</sup>)<sup>''b''</sup> + 1 ≡ (−1)<sup>''b''</sup> + 1 ≡ 0('''mod''' 2<sup>''a''</sup> + 1)，即2<sup>''a''</sup> + 1系2<sup>''n''</sup> + 1嘅因數。）也就系講，所有具有形式2<sup>''n''</sup> + 1嘅素數必然系費馬數，呢些素數稱為'''費馬素數'''。已知嘅費馬素數只有''F''<sub>0</sub>至''F''<sub>4</sub>五個。

==基本性質==

費馬數滿足以下嘅[[遞回關系]]：

:<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>

其中''n'' ≥ 2。呢些等式都可以用[[數學歸納法]]推出。從最後一個等式中，我哋可以推出'''哥德巴赫定理'''：任何兩個費馬數都冇大於1嘅[[公因子]]。要推出呢個，我哋需要假設 0 ≤ ''i'' < ''j'' 且 ''F''<sub>''i''</sub> 和 ''F''<sub>''j''</sub> 有一個公因子 ''a'' > 1。咁 ''a'' 能把

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

其他性質：
*''F''<sub>''n''</sub>嘅位數''D''(''n'',''b'')可以表示成以''b'' 為[[進位制|基數]]就系
*除咗F<sub>1</sub> = 2 + 3以外冇費馬數可以表示成兩個[[素數]]嘅和。
*當''p''系奇素數陣，冇費馬數可以表示成兩個數嘅''p''次方相減嘅形式。
*除咗F<sub>0</sub>和F<sub>1</sub>，費馬數嘅最後一位系7。
* 所有費馬數{{OEIS|id=A051158}}嘅倒數之和系[[無理數]]。 ([[Solomon W. Golomb]], 1963)

==最小嘅費馬數==

[[3]]、[[5]]、[[17]]、[[257]]、[[65537]]、[[4294967297]]、[[18446744073709551617]]{{OEIS|id=A000215}}。


== 素性檢驗 ==

設<math>F_n=2^{2^n}+1</math>為第''n''個費馬數。如果''n''唔等於零，咁：

:<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>，因此滿足3<sup>k</sup>=1（mod<math>F_n</math>）嘅最小整數k一定整除<math>F_n-1=2^{2^n}</math>，佢系2嘅冪。另一方面，k唔得整除<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>。

[[Category:整數數列|Fermat]]
[[Category:數學中未解決嘅問題]]
[[Category:大數]]