欧几里得证明：素数有无穷多个

大约在公元前 300 年，欧几里得写下了一个短到只需一段话的论证，从此再未被超越，因为它根本无法被超越。命题是：素数无穷无尽。证明是一个构造：给我任意一份有限素数列表，我还你一个不在上面的素数。

两千年后，这个论证依然带着魔术般的质感。每一步都看得清清楚楚，知道结局在哪里，它依然能让你心头一震。

什么是素数，为何值得追问

素数是大于 1 的整数，它除了 1 和自身没有其他因数。最初几个是 2、3、5、7、11、13。它们嵌在整数里，像原子：所有其他整数都是把素数相乘造出来的。比如 30 分解为 2 乘 3 乘 5，而且基本只有这一种分解方式。

既然素数是所有整数的构件，自然会问：它们会用完吗？有没有一个最大的素数，越过它之后就再无更多？欧几里得的回答是否定的，他所走的路径优美到可以一口气读完。

设定：假设列表是完整的

这个论证是反证法，你先把对方想要的一切都给他。

现在，把所有素数集齐之后，用它们构造一个新数。

构造打破列表的数

这是关键步骤，值得放慢来看清楚它做了什么。把所有列出的素数相乘，得到一个能被列表上每个素数整除的数。加上 1，则同时破坏了所有这些整除关系。

用 N 除以 p1，余数是 1，因为乘积 (p1 × p2 × ... × pk) 可以被 p1 整除，加上 1 把余数变成了 1。同样的逻辑适用于 p2、p3，以及列表上每一个素数。它们都不能整除 N。

矛盾

让证明更诚实的反例

很多关于欧几里得证明的通俗介绍在这里出了问题：它们声称 N 本身总是素数，事实并非如此，这个区别很重要。

取列表 「2, 3, 5, 7, 11, 13」。乘积是 2 × 3 × 5 × 7 × 11 × 13 = 30030，加 1 得到 N = 30031。

30031 是素数吗？不是。

30031 = 59 × 509。

59 和 509 都是素数，都不在列表 「2, 3, 5, 7, 11, 13」 中。这正是证明所预测的：不是 N 本身是素数，而是 N 的素因子不在列表里。在这个例子中，素因子是 59 和 509，两个被有限列表遗漏的素数。论证成立，但成立的依据来自因子，而非 N 本身。

证明实际说的是什么

值得停下来看清楚这个论证的形状，因为它异常干净。

你并没有明确构造出那个缺失的素数，也没有去搜寻它，而是证明了它必然存在：假设它不存在，就会走进逻辑的死胡同。藏在 N 的因子里的素数 q，可能很容易找到（就像尝试几个小因子就能发现 30031 = 59 × 509），也可能极其巨大。证明对此毫不在意，它的力量来自必然性：无论你交出什么列表，构造过程都能找到空缺。

这自然地连接到同一精神的其他证明：假设反面，看它崩塌。康托尔对角线论证在更大的尺度上使用了同样的结构：假设实数的完整列表存在，然后构造出一个可证明不在其中的实数。欧几里得的回声清晰可辨。

为什么素数永远不会彻底稀疏

这个证明没有告诉你素数之间的间距可以多大，也没有告诉你给定范围后下一个素数有多大。欧几里得的论证只保证存在性：在任何有限集合之外，还有另一个素数在等待。素数在数轴上的分布是一个困难得多的问题，至今仍是数学中最深刻的开放领域之一。

证明告诉你的是结构性的东西：素数无法被任何有限手段穷尽。你可以用一生来列举素数，始终是在列举一个无穷的剩余。你找到的每一个素数都是真实的，但你前方的那些同样真实、同样众多，同样无法被有限列表触及。

要感受用乘法和指数构建时数字能多快增长，直观理解指数一文是自然的伴侣：乘积 p1 × p2 × ... × pk 的增长速度可能超出你的预期，而这种增长正是 N 迅速变得巨大的原因之一。

禅意

欧几里得的证明已有两千多年历史，此后数学家们找到了数百个相同结论的证明。没有哪一个让这个证明过时，因为它留在这里靠的不是最聪明或最一般化，而是最透明。

你一遍就能看清整个论证。构造是自然的，矛盾是尖锐的，没有任何一步需要你靠信念接受，或相信某台复杂机器在按说明运转。

证明要你记住的是一个单一的念头：任何有限素数列表，都已经不完整。不是因为列表选得不好，而是素数本身是那种无法被任何有限数目所包容的东西。它们属于无穷，就像整数属于无穷，就像分数属于无穷，就像直线上的点属于无穷。证明不告诉你下一个素数在哪里，它告诉你：下一个素数总在那里。

这就够了，一直以来都够了。

要感受这种必然性精神中的其他结果，古德斯坦定理表明一个数列尽管增长到无法书写的高度，却总会归零，使用的正是同一种逻辑：「某件事必定发生，因为另一种情形是不可能的。」这个论证家族值得了解，每一个都是同一基础事实的不同角度：数学没有后门，结构永远成立。