证明不存在最大素数

本周我们将继续探索数学证明。今天我们将讨论一个常见的证明：不存在最大的质数。和往常一样，我的目标是尽可能用简单的语言解释，避免使用复杂的数学符号。不过，在此之前，我先给大家带来每周例行的逻辑谜题。

逻辑谜题

你身处一栋106层高的建筑中。楼层编号为0到105（除美国以外，世界大部分地区都采用这种楼层编号方式）。你想测试一下，从哪一层可以安全地将鸡蛋扔进地面上一个装满羽毛的大盒子里。你知道从楼顶扔下的鸡蛋会碎，而从0层扔下的鸡蛋不会碎。你有两个鸡蛋可以用来做实验。在最坏的情况下，你最少需要扔多少次才能让鸡蛋落入地面？

答案和解析出现在本栏的末尾。

证明不存在最大素数

我将用反证法证明不存在最大素数。换句话说，我将反驳相反的结论——即存在最大素数。

我们把最大的素数称为_{p_n} ，这意味着它是第 n 个素数，让我们按如下顺序标记所有素数：

_p1 = 2， _p2 = 3， _p3 = 5， _p4 = 7，… _pn = ?

考虑如下的数字 N：

N = p ₁ × p ₂ × p ₃ × p ₄ × … × p _n + 1。

如果 N 是素数，那么没有比它小的素数能整除它。但是，如果我们用它整除任何小于等于_p的素数，余数都是 1。这只能用两种方式解释：

1. N 本身是素数，它一定大于 p _n 。
2. 存在大于 p _{n 的}素数，能整除 N。

无论如何，我们已经证明存在比 p _n更大的素数。

我们来看一个例子，比如一个较小的素数。假设 31 是最大的素数，我来看看会发生什么。在这种情况下：

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1,805,044,411,171

使用质因数计算器，我们发现 1,805,044,411,171 = 1,061,729 × 1,700,099。因此，我们找到了两个比 31 大的质数：1,061,729 和 1,700,099。

再举一个例子，假设7是最大的质数。那么N = 2×3×5×7 + 1 = 211。对211进行质因数分解检验，我们发现211是质数。因此，我们找到了一个比7更大的质数。

无论我们假设哪个素数最大，这种方法都会找到一个更大的素数。

逻辑谜题的答案

14

以下是如何在不超过 14 次跳跃的情况下找到最高安全楼层的方法。

1. 从14楼扔下第一个蛋。如果蛋碎了，则依次测试1楼到13楼。如果蛋碎了，最多需要扔14次（第一个蛋扔1次，第二个蛋扔13次）。否则，返回步骤2。
2. 向上爬13层，从27层扔下第一个蛋。如果蛋碎了，则逐层测试15层到26层。如果蛋碎了，最多需要扔14次（第一个蛋需要扔2次，第二个蛋最多需要扔12次）。否则，返回步骤3。
3. 向上走12层，从39层扔下第一个蛋。如果蛋碎了，就逐层测试28层到38层。如果蛋碎了，最多需要扔14次（第一个蛋3次，第二个蛋最多11次）。否则，返回步骤4。
4. 向上攀爬11层，从第50层扔下第一个蛋。如果蛋碎了，则逐层测试第40层到第49层。如果蛋碎了，最多需要扔14次（第一个蛋4次，第二个蛋最多10次）。否则，返回步骤5。
5. 向上爬10层，从第60层扔下第一个蛋。如果蛋碎了，就逐层测试第51层到第59层。如果蛋壳破裂，最多需要滴落 14 滴（第一个蛋需要 5 滴，第二个蛋最多需要 9 滴）。否则，请转至步骤 6。
6. 向上走9层，从69层扔下第一个蛋。如果蛋碎了，则逐层测试61层到68层。如果蛋碎了，最多需要扔14次（第一个蛋6次，第二个蛋最多8次）。否则，转到步骤7。
7. 向上攀爬8层，从77层扔下第一个蛋。如果蛋碎了，则逐层测试70层到76层。如果蛋碎了，最多需要扔14次（第一个蛋7次，第二个蛋最多7次）。否则，返回步骤8。
8. 向上攀爬7层，从第84层扔下第一个蛋。如果蛋碎了，则逐层测试第78层到第83层。如果蛋碎了，最多需要扔14次（第一个蛋需要扔8次，第二个蛋最多需要扔6次）。否则，进行步骤9。
9. 向上走6层，从90层扔下第一个蛋。如果蛋碎了，就逐层测试85层到89层。如果蛋碎了，最多需要扔14次（第一个蛋9次，第二个蛋最多5次）。否则，转到步骤10。
10. 向上走5层，从95层扔下第一个蛋。如果蛋碎了，就逐层测试91层到94层。如果蛋碎了，最多需要扔14次（第一个蛋10次，第二个蛋最多4次）。否则，转到步骤11。
11. 向上走4层，从99层扔下第一个蛋。如果蛋碎了，就逐层测试96层到98层。如果蛋碎了，最多需要扔14次（第一个蛋需要扔11次，第二个蛋最多需要扔3次）。否则，转到步骤12。
12. 向上走三层，从102层扔下第一个蛋。如果蛋碎了，就依次测试100层和101层。如果蛋碎了，最多需要扔14次（第一个蛋需要扔12次，第二个蛋最多需要扔2次）。否则，转到步骤13。
13. 上两层楼，从104层扔下第一个蛋。如果蛋碎了，就测试103层。如果蛋碎了，最多需要扔14次（第一个蛋13次，第二个蛋1次）。否则，跳到步骤14。
14. 上一层楼，从105层扔下第一个蛋。如果蛋碎了，最高的安全楼层是104层。如果蛋没碎，最高的安全楼层是105层。

对于一座n层建筑，一般策略是找到进行第一次坠落的最佳楼层。如果第一次测试通过，则从该楼层向上移动相同层数减1的楼层。如果第二次测试通过，则再次向上移动，但这次的楼层数比上次向上移动的楼层数少1层。如此反复，每次测试之间向上移动的楼层数都比前一次少1层。如果第一次测试失败，则使用第二个蛋，从该层数范围内最低的楼层开始，系统地测试最后两次测试之间的每一层。

注意楼层数的增加顺序为 n、n-1、n-2、……1。所有这些增加的总和为 n(n+1)/2。关键在于找到 n 的最小整数值，使得级数之和等于或大于建筑物的楼层数。

例如，我们来看一座 500 层高的建筑（不包括安全的底层），求解：

n(n+1)/2 = 500

n(n+1) = 1000

^n² + n - 1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">使用勾股定理：

n = (-1 +/- √4001 )/2 ≈ 31.13

然而，楼层数均为整数。因此，我们向上取整至 n=32。所以，对于 500 层楼（如果算上安全的底层，则为 501 层），我们从第 32 层开始进行第一次测试。