費馬數

模:UnCantonese 費馬數系以數學家費馬命名一組自然數，具有形式：

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

其中n為非負整數。

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

基本性質

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

$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 ≥ 2。呢些等式都可以用數學歸納法推出。從最後一個等式中，我哋可以推出哥德巴赫定理：任何兩個費馬數都冇大於1嘅公因子。要推出呢個，我哋需要假設 0 ≤ i < j 且 F_i 和 F_j 有一個公因子 a > 1。咁 a 能把

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

其他性質：

• F_n嘅位數D(n,b)可以表示成以b 為基數就系
• 除咗F₁ = 2 + 3以外冇費馬數可以表示成兩個素數嘅和。
• 當p系奇素數陣，冇費馬數可以表示成兩個數嘅p次方相減嘅形式。
• 除咗F₀和F₁，費馬數嘅最後一位系7。
• 所有費馬數模:OEIS嘅倒數之和系無理數。 (Solomon W. Golomb, 1963)

最小嘅費馬數

3、5、17、257、65537、4294967297、18446744073709551617模:OEIS。

素性檢驗

設$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}\equiv 1{\pmod {F_{n}}}$，因此滿足3^k=1（mod$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({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}$,

其中$\left({\frac {3}{F_{n}}}\right)$系勒讓德符號。利用重復平方，我哋可以發現$2^{2^{n}}\equiv 1{\pmod {3}}$，因此$F_{n}\equiv 2{\pmod {3}}$，以及$\left({\frac {F_{n}}{3}}\right)=-1$。因為$F_{n}\equiv 1{\pmod {4}}$，根據二次互反律，我哋便可以得出結論$\left({\frac {3}{F_{n}}}\right)=-1$。