2002 STEP II Q3 —— 质数有无穷多个的一种证明

本篇介绍一种利用费马数（Fermat number）来证明质数有无穷多个的巧妙构思，问题来自于 2002 STEP II 数学考试中的第3题。

STEP (Sixth Term Examination Paper) 是英国剑桥考试中心为本科申请者提供的数学专项考试，通常会是剑桥、帝国理工、伦敦大学、华威等名校的数学、计算机、工程等专业的录取要求之一。每年都会有一些非常精彩的考题，我在此挑选一些个人喜欢的考题作分享。

问题原题

问题翻译

定义费马数列 \(\{F_0, F_1, \cdots, F_n, \cdots \}\)，其中第 \(n\) 个元素由以下公式给出

\[F_n = 2^{2^n}+1 \qquad (n=0,1,2,\cdots)\]

(1) 证明：对 \(k\geq 1\)，有

\[F_0 F_1 \cdots F_{k-1} = F_k -2 \quad (*)\]

(2) 论证任意两个费马数不可能存在大于1的公因数，从而论证质数有无穷多个。

参考解答

(1)

(\(*\)) 式可以有很多种漂亮的证明方式。

直接证明并不麻烦。注意到，\(2^{2^0}-1 = 2^1 -1 = 1\)，于是

\[\begin{aligned} F_0 F_1 \cdots F_{k-1} &= 1\times F_0 F_1 \cdots F_{k-1} \\ &= \left(2^{2^0}-1 \right) \times \left(2^{2^0}+1 \right) \times \left(2^{2^1}+1 \right) \times \cdots\times \left(2^{2^{k-1}}+1 \right) \\ &= \left(2^{2^1}-1 \right) \times \left(2^{2^1}+1 \right) \times \cdots\times \left(2^{2^{k-1}}+1 \right) \\ & = \left(2^{2^{k-1}}-1 \right) \times \left(2^{2^{k-1}}+1 \right) \\ & = 2^{2^{k}}-1 \\ &= \left(2^{2^{k}}+1 \right) -2 \\ &= F_k -2 \end{aligned}\]

或者也可以更加无脑地采用数学归纳法。

\[\begin{aligned} F_0 &= 2^{2^0}+1 = 2^1+1 = 3 \\ F_1 &= 2^{2^1}+1 = 2^2+1 = 5 \\ F_2 &= 2^{2^2}+1 = 2^4+1 = 17 \\ F_3 &= 2^{2^3}+1 = 2^8+1 = 257 \\ &\cdots \end{aligned}\]

不难验证

\[\begin{aligned} F_0 F_1 &= 3\times 5 = 15 = 17-2 = F_2 - 2 \\ F_0 F_1 F_2 &= 3\times5\times17 = 255 = 257 - 2 = F_3 -2 \\ & \cdots \end{aligned}\]

假设 \(F_0 F_1 \cdots F_{k-1} = F_k -2\) 对 \(k\leq t\) 均成立，那么当 \(k=t+1\) 时

\[\begin{aligned} F_0 F_1 \cdots F_{t-1} F_t &= (F_t -2) \times F_t \\ & = \left(2^{2^{t}}+1 -2 \right) \times \left(2^{2^{t}}+1 \right) \\ &= \left(2^{2^{t}} \right)^2 -1 \\ &= 2^{2^{t+1}} - 1 \\ &= \left(2^{2^{t+1}} + 1\right) - 2 \\ &= F_{t+1} - 2 \end{aligned}\]

因此根据数学归纳法，\(F_0 F_1 \cdots F_{k-1} = F_k -2\) 对任意 \(k\geq1\) 恒成立。

(2)

利用反证法，我们假设两个费马数 \(F_m\) 与 \(F_n\) 存在公因数 \(p>1\)，然后导出逻辑矛盾。

不失普遍性，设 \(n>m\)，那么根据假设

\[F_0F_1 \cdots F_m \cdots F_{n-1} \mod p = 0\]

另一方面，\(F_n\) 也有同样的因子 \(p\)，即

\[F_n \mod p = 0\]

于是

\[F_n - F_0F_1\cdots F_{n-1} \mod p =0\]

根据 (\(*\)) 式，这说明 \(2\text{ mod } p=0\)，唯一的可能只有 \(p=2\)。但是从费马数的定义可以立即看出，所有费马数都是奇数，不可能有 2 这个因子，出现矛盾。因此原假设不成立，故任意两个费马数不可能存在大于1的公因数。

因此对于费马数列 \(\{F_0, F_1, \cdots, F_n, \cdots \}\)，每一项所含有的质数因子都与前面的项含有的质数因子不同，也就是每往后一项，总可以带出新的质数因子。根据构造，费马数有无穷多个，所以质数必然也有无穷多个。

问题原题

问题翻译

参考解答

(1)

(2)

推荐阅读