问题及解答

Fermat number 指形如 $2^{2^n}+1$ 的正整数. 它有如下性质:

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

(2) $F_n=F_{n-1}+2^{2^{n-1}}\cdot F_0\cdots F_{n-2}$

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

(4) $F_n=F_0\cdots F_{n-1}+2$

由 (4) 可推出 Goldbach 定理: 任意两个不同的 Fermat 数没有共同的因子.

也就是说 Fermat 数之间是互素的.

References:

https://en.wikipedia.org/wiki/Fermat_number#Generalized_Fermat_primes

:: F E R M A T S E A R C H . O R G :: News

(1)

\[
RHS=(2^{2^{n-1}}+1-1)^2+1=(2^{2^{n-1}})^2+1=2^{2^{n-1}\cdot 2}+1=2^{2^n}+1=F_n=LHS.
\]

(2)

容易验证公式对于 $n=1,2$ 均成立.

用归纳法证明. 假设对于 $n=k$, 有

\[
F_k=F_{k-1}+2^{2^{k-1}}\cdot F_0\cdots F_{k-2}
\]

则, 当 $n=k+1$ 时,

\[
\begin{split}
F_{k+1}&=(F_k -1)^2+1\\
​&=(F_{k-1}-1+2^{2^{k-1}}\cdot F_0\cdots F_{k-2})^2 +1\\
​&=(F_{k-1}-1)^2+2(F_{k-1}-1)\cdot 2^{2^{k-1}}\cdot F_0\cdots F_{k-2}+(2^{2^{k-1}})^2\cdot F_0^2\cdots F_{k-2}^2+1\\
​&=[(F_{k-1}-1)^2+1]+2^{2^{k-1}+1}\cdot F_0\cdots F_{k-2}(F_{k-1}-1)+2^{2^{k-1}\cdot 2}\cdot F_0^2\cdots F_{k-2}^2\\
​&=F_k+2^{2^{k-1}+1}\cdot F_0\cdots F_{k-2}(F_{k-1}-1)+2^{2^k}\cdot F_0^2\cdots F_{k-2}^2\\
​&=F_k+2^{2^k}\cdot F_0\cdots F_{k-2}\Bigl(\frac{1}{2^{2^{k-1}-1}}(F_{k-1}-1)+F_0\cdots F_{k-2}\Bigr)\\
​\end{split}
\]

其中

\[
\begin{split}
​\frac{1}{2^{2^{k-1}-1}}(F_{k-1}-1)+F_0\cdots F_{k-2}&=\frac{1}{2^{2^{k-1}}}\Bigl(2(F_{k-1}-1)+2^{2^{k-1}}F_0\cdots F_{k-2}\Bigr)\\
&=\frac{1}{2^{2^{k-1}}}\Bigl(F_{k-1}+2^{2^{k-1}}F_0\cdots F_{k-2}+F_{k-1}-2\Bigr)\\
&=\frac{1}{2^{2^{k-1}}}\Bigl(F_k+F_{k-1}-2\Bigr)\\
&=\frac{1}{2^{2^{k-1}}}\Bigl(2^{2^k}+2^{2^{k-1}}\Bigr)\\
​&=\frac{1}{2^{2^{k-1}}}\cdot 2^{2^{k-1}}\Bigl(2^{2^{k-1}}+1\Bigr)\\
​&=F_{k-1},
​\end{split}
\]

故

\[F_{k+1}=F_k+2^{2^k}\cdot F_0\cdots F_{k-2}\cdot F_{k-1}.\]

(3)

根据 (1), $F_n=(F_{n-1}-1)^2+1=F_{n-1}^2-2F_{n-1}+2$, 而 $F_{n-1}=(F_{n-2}-1)^2+1$, 代入得

$F_n=F_{n-1}^2-2\Bigl((F_{n-2}-1)^2+1\Bigr)+2=F_{n-1}^2-2(F_{n-2}-1)^2$.

(4)

根据 (1),

\[
\begin{split}
​F_{k+1}&=(F_k-1)^2+1\\
&=F_k^2 -2F_k+2\\
​&=F_k(2^{2^k}+1)-2(F_k-1)\\
​&=F_k+2^{2^k}F_k-2\cdot 2^{2^k}\\
​&=F_k+2^{2^k}\cdot(F_k-2),
​\end{split}
\]

另一方面, 根据 (2) $F_{k+1}=F_k+2^{2^k}\cdot F_0\cdots F_{k-1}$, 因此, 我们有 $F_k-2=F_0\cdots F_{k-1}$, 即

\[
F_k=F_0\cdots F_{k-1}+2.
\]