有趣的费马数

大家好，欢迎来到IT知识分享网。

话题：#数学# #初等数论#

小石头/编

皮埃尔·德·费马（1601年8月17日—1665年1月12日）正是这个狂潮中的佼佼者，作为一个全职律师的它，用业余时间研究数学，并取得了丰硕的成果。

有一天，费马拿到了 丢潘图 所著的 《算术》一书，从此开启了 他的数论研究。古希腊人早就通过下面的构造法证明了：

• 素数有无穷多个。

证：

假设 素数有限，可记 P = {p₁, p₂, …, pₙ} 为全部的素数，于是构造一个数，

q = p₁p₂⋯pₙ + 1

它显然不能被 P 中 任意的 素数 整除，于是 q 也是素数，可是 q 又不是属于 P 这与 P 是全体素数 的设定 矛盾！▌

既然，素数有无穷多个，于是费马就想要找到，一个全部是 素数的 无穷数列，经过一番思索，费马给出了 费马数 的定义：

• Fₙ＝2²ˆⁿ + 1 (n≥0)

由于 2 的 2ⁿ 次方 一定是偶数，所以 费马数 一定是 奇数。

费马，对前五个费马数进行了计算，

F₀＝2²ˆ⁰ + 1＝2¹ + 1＝2 + 1 = 3

F₁＝2²ˆ¹ + 1＝2² + 1＝ 4 + 1 = 5

F₂＝2²ˆ² + 1＝2⁴ + 1＝ 16 + 1 = 17

F₃＝2²ˆ³ + 1＝2⁸ + 1＝256 + 1 = 257

F₄＝2²ˆ⁴ + 1＝2¹⁶ + 1＝65536 + 1 = 65537

并经过计算验证，发现它们都是素数，于是就高兴的认为自己找到了 想要的 数列。

不过，好景不长，大约一百多年后，莱昂哈德·欧拉（1707年4月15日—1783年9月18日）就发现，

F₅ = 641 ⋅

是一个合数，从而让费马数的美梦破碎。

之后，更多的数学家对于 之后的 更多 费马数 进行了 验证，就 目前 验证过的结果 都是 合数，还没有找到素数，现在，

• 费马数是否含有无穷多个素数？

甚至，

• 费马数是否含有无穷多个合数 ？

都还是未解之谜！

当然，这些谜团，还不足以体现费马数的有趣性。数学家观察发现，

F₁＝ 3 + 2 = F₀ + 2

F₂＝ 3⋅5 + 2 = F₀F₁ + 2

F₃ = 3⋅5⋅17 + 2 = F₀F₁F₂ + 2

于是猜想：

• Fₙ＝F₀F₁⋅⋅⋅Fₙ₋₁ + 2 (n≥1) ； Ⓐ

归纳假设 Ⓐ 成立，于是有，

Fₙ₊₁ ＝ 2²ˆ⁽ⁿ⁺¹⁾ + 1 ＝ 2²⁽²ˆⁿ⁾ + 1 ＝ (2²ˆⁿ)² + 1＝ (2²ˆⁿ + 1 – 1)² + 1 ＝ (Fₙ – 1)² + 1 ＝ Fₙ² – 2Fₙ + 1 + 1＝Fₙ² – 2Fₙ + 2＝ (Fₙ – 2)Fₙ + 2＝ (F₀F₁⋅⋅⋅Fₙ₋₁ + 2 – 2)Fₙ + 2 = F₀F₁⋅⋅⋅Fₙ₋₁Fₙ + 2

这样 Ⓐ就归纳得证。

由 Ⓐ 有，

Fₙ – 2 = F₀F₁⋅⋅⋅Fₙ₋₁

对于 任意两个 费马数 Fₘ 和 Fₙ，不妨设, m < n，于是根据上式，Fₘ 整除 Fₙ – 2，即，

Fₘ | Fₙ – 2，

又设 d 是 Fₘ 整除 Fₙ 的最大公因数，即，

d = (Fₘ, Fₙ)

于是，

d | Fₘ | Fₙ – 2， d | Fₙ

进而，

d | Fₙ – (Fₙ – 2) = 2

这说明 d = 1 或 2， 可是，Fₙ 是奇数，不可能还有 2 这个因数，于是 只能 d = 1，即，

(Fₘ, Fₙ) = 1

这样就证明了：

• 任意两个 费马数 互素。 Ⓑ

由这个性质，若 我们从 每个 Fₙ 费马数 中 找到一个 素因子 pₙ，则各个 pₙ 一定不同，因为 Fₙ 是无穷多个，所以 pₙ 也是无穷多个，于是 我们就是神奇的证明了：素数有无穷多个。

上文中使用的数学概念：

• 对于 任意 整数 a, b，若存在 整数 c 使得 ac = b，则称 a 整除 b ，记为 a | b ，同时称 a 是 b 的因数， b 是 a 的 倍数，（否则 称 a 不整除 b，记为 a ∤ b）；
• 若 p 只有 1 或 p 这两个 因数，称为 p 为素数。
• 称 a 与 b 的 最大公共因数，为 a 与 b 的最大公因数，记为 (a, b)，当 (a, b) = 1时，称 a 与 b 互素；

坊间相传，欧拉是利用自己庞大的心算能力，找到了 F₅ 含有 641 这个因子，但实际上，仅有心算能力 还不行，因为，

F₅＝2²ˆ⁵ + 1 = 2³² + 1 = + 1 =

是如此的巨大，有再强的心算能力，从 3 开始 一一验证，来 找到 F₅ 的因子 641 ，那要算到猴年马月去了。真实情况是，欧拉先发现了，

• 当 n ≥ 2 时，Fₙ 的任何一个因子，一定可以表示为 2ⁿ⁺²k + 1； Ⓒ

例如，对于 F₂ ，因子有，

1 = 2²⁺²⋅0 + 1

17 = 2²⁺²⋅1 + 1

对于 F₃ ，因子有，

1 = 2³⁺²⋅0 + 1

257 = 2³⁺²⋅8 + 1

因此，

F₅ 的因子 必然是，

2⁵⁺²k + 1 = 2⁷k + 1 = 128k + 1

于是 欧拉 只需要 从 k = 1 开始尝试，当 验证到 k = 5 ，即 128⋅5 + 1 = 641， 时，就发现了 这个因子。也就是说，欧拉仅仅做了 五次验证。

若令 K = 2ⁿk，则 2ⁿ⁺²k + 1 = 4K + 1，于是 ③ 说明 从 F₂ 开始 费马数的 因子 一定是 4K + 1 型，进而 其素因子 一定是 4K + 1 型素数，而由 Ⓑ 知道，从 F₂ 开始 每个 费马数 Fᵢ 中 取 一个 素因子 pᵢ 组成的无穷素数序列的各项皆不相同，这样就证明了：

• 4K + 1 型素数 有无穷多个。

最后，我们来看一下，欧拉是如何发现 Ⓒ 的。

首先，只需要证明 素因子的情况，因为：合数因子 a 是 素因子的乘积，不妨设 a = p₁p₂，只要能证明，

p₁ = 2ⁿ⁺²k₁ + 1 ，p₂ = 2ⁿ⁺²k₂ + 1

则，

a = (2ⁿ⁺²k₁ + 1)(2ⁿ⁺²k₂ + 1) = 2ⁿ⁺²2ⁿ⁺²k₁k₂ + 2ⁿ⁺²k₁ + 2ⁿ⁺²k₂ + 1 = 2ⁿ⁺²(2ⁿ⁺²k₁k₂ + k₁ + k₂) + 1

于是 令 k = 2ⁿ⁺²k₁k₂ + k₁ + k₂，就有 a = 2ⁿ⁺²k + 1。

然后，设 p 是素数，是 Fₙ＝2²ˆⁿ + 1 的因子，于是 Fₙ 模 p 余 0，即，

Fₙ = 2²ˆⁿ + 1 ≡ 0 (mod p)

同余等式两边同时 减 1，有，

2²ˆⁿ + 1 – 1 = 2²ˆⁿ ≡ 0 – 1 = -1 (mod p)

即，

2²ˆⁿ ≡ – 1 (mod p) ①

再两边同时平方，有，

(2²ˆⁿ)² = 2²˙²ˆⁿ = 2²ˆ⁽ⁿ⁺¹⁾ ≡ (-1)² = 1

即，

2²ˆ⁽ⁿ⁺¹⁾ ≡ 1 (mod p) ②

对于 任意 正整数 m，以及素数 p，若 (m, p) = 1，则必然存在 整数 d 满足，

mᵈ ≡ 1 (mod p)

我们 称满足上式的 最小的 那个 d 为 m 模 p 的 阶，可以证明：

• 对任意 满足 mᵃ ≡ 1 (mod p) 的 a 必有 d|a ；③

于是，若设 d 是 2 模 p 的阶，则 ② ③ 相结合，就得到，

d | 2⁽ⁿ⁺¹⁾

又 d ∤ 2ⁿ ，因为：若 d | 2ⁿ 则有 dc = 2ⁿ，于是，

2²ˆⁿ = 2ᵈᶜ = (2ᵈ)ᶜ ≡ (1)ᶜ = 1 (mod p)

进而联立 ① 有，

1 ≡ 2²ˆⁿ ≡ -1 (mod p)

即，

1 ≡ -1 (mod p) ④

于是，

1 = -1 + kp

kp = 2

这说明

p|2

而 p 是素数，于是

p = 2

可是，Fₙ 是奇数，不可能有 2 这个偶因子，于是 ④ 不成立，矛盾！

由 d | 2⁽ⁿ⁺¹⁾ 知道 d = 2ᵏ，k ≤ n+1，又由 d ∤ 2ⁿ 知道 k > n，于是只能 k = n+1，即，d = 2ⁿ⁺¹。

再根据费马小定理：

• 设 p 是素数，对于任意整数 a，若 p ∤ a ，则有 aᵖ⁻¹ ≡ 1（mod p）；

有，

2ᵖ⁻¹ ≡ 1 (mod p)

于是结合 ③，得到，

d | p – 1

即，

2ⁿ⁺¹ | p – 1

于是可以得到，

p – 1 = 2ⁿ⁺¹k

即，

p = 2ⁿ⁺¹k + 1 ⑤

这距离 Ⓒ 还差一点，但是用于 找 641 也只需要沿着到 k = 10，仅多算了五次。

对于 整数 m 和 n，若 存在 整数 x 使得，

x² ≡ n (mod m)

称 n 是 模 m 的 二次剩余。对于奇素数 p，(n, p) = 1，引入勒让德符号：

欧拉发现了如下的著名判别式：

同时，显然 当 n ≥ 2 时，由 ⑤ 有，

p ≡ 1 (mod 8)

而 欧拉又证明了，

于是，综上有，

2⁽ᵖ⁻¹⁾ᐟ² ≡ (2 | p) = 1 (mod p)

这样再结合 ③ 就有，

d | (p – 1)/2

即，

2ⁿ⁺¹ | (p – 1)/2

于是可以得到，

(p – 1)/2 = 2ⁿ⁺¹k

故，

p = 2·2ⁿ⁺¹k + 1 =2ⁿ⁺²k + 1

这就是 Ⓒ 了。

上文中使用的定理证明 大家可以参考 任意一本 《初等数论》的教材，这里小石头就不再累述了。

（今天就写到这里，关于 费马数 的有趣之处，不仅仅这么多，以后有时间，小石头 再和大家讨论！）

费马数 如此的 简单 而又 神秘，各位 有没有兴趣，自己对其 探索一番？例如：目前验证过的最大费马数 是 F₂₁₄₅₃₅₁，是一个合数，你还能检验出更大的 费马数 吗？