費馬數

費馬數係以數學家費馬命名嘅一組自然數，佢嘅樣係：

$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=0(\mod 2^{n}+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\geq 2$。呢些等式都可以用數學歸納法推論出嚟。由最後一個等式中，我哋可以推出哥德巴赫定理：任何兩個費馬數都冇大於1嘅公因子。要推論出呢個，我哋需要假設 $0\leq i<j$ ，而且 $F_{i}$ 同埋 $F_{j}$ 有一個公因數 $a>1$。咁 $a$ 可以將

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

其他性質：

• $F_{n}$ 嘅位數 $D$($n,b$)可以表示成以 $b$ 做基數嘅樣。
• 除咗 $F_{1}=2+3$ 以外冇費馬數可以表示成兩個質數嘅和。
• 當 $p$ 係奇質數陣，冇費馬數可以表示成兩個數嘅 $p$ 次方相減嘅形式。
• 除咗 $F_{0}$ 和 $F_{1}$，費馬數嘅最後一位係 $7$。
• 所有費馬數（OEIS數列A051158）嘅倒數之和係無理數。 (Solomon W. Golomb, 1963)

最小嘅費馬數

3、5、17、257、65537、4294967297、18446744073709551617（OEIS數列A000215）。

素性檢驗

假設$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$。