埃尔德什对素数无穷性的证明

luyuanhong

埃尔德什对素数无穷性的证明

原创 围城里的猫 MathSpark 2024 年 07 月 07 日 07:30 陕西

今天这期让我们看一看著名数学家埃尔德什给出的关于素数有无穷多个的证明。好了闲话少说让我开始吧。



因式分解的变体

根据算术基本定理（算术基本定理的应用—— 2 的平方根是无理数），我们可以将任何大于 1 的整数写成素数的乘积。例如，45 = 5×3^2 ，100 = 2^2×5^2 。



我们可以将这个定理稍微改变一下叙述，即任何大于 1 的整数都可以写成无平方数 s 与平方数 r^2 的乘积，而且可以唯一地做到这一点。无平方数是指没有完全平方数可以整除它的数。我将其称为数字的 sr^2 形式。

例如，12 不是无平方数，因为 4 可以整除它。要将 12 转换为 sr^2 形式，我们写为 12 = 3×2^2 = sr^2 ，其中 s=3 ，r=2 。

这一结果很好地遵循了算术基本定理。如果我们有一个数字，例如 3^4×2^5×7^3 ，我们将其写为 sr^2 = (2×7)×(3^2×2^2×7)^2 ，其中 s = 2×7 ，r = 3^2×2^2×7 。

本质上，如果素数 p 的奇数次方，比如 p^7 ，显然我们可以写成 p^7 = p^6×p = (p^3)^2×p 。我们可以对每个素因数重复此操作，就可以写成 sr^2 的形式。

再举一个例子，5145 = 3×5×7^3 = sr^2 =(3×5×7)×(7)^2 。

证明

埃尔德什说我们应该将数字分解为 sr^2 形式。我们先从一个算例开始，然后进行抽象证明。如果你觉得纯抽象的证明太令人困惑，那么具体的例子包括证明的所有关键思想，但使用了实际的数字，这样你就可以更轻松地理解。

示例

我们利用反证法，假设只有 4 个素数，即 2、3、5、7 。让我们看看所有小于 10000 的数字。所有这些都以 sr^2 形式写出。对于 r 的值，只有 100 种选择。这是因为如果 r=101 ，则 r^2 = 101^2 = 10201 ，大于 10000 ，因此不能成为小于 10000 的数字的除数。

那么我们的无平方数的选择数量是多少呢？让我们来看看。对于任何素数 p ，我们可以将其包括在内，也可以不包含。这意味着有 16 = 2^4 种可能的方法来构建无平方数：{2}、{3}、{5}、{7}、{2×3}、{2×5}、{2×7}、{3×5}、{3×7}、{5×7}、{2×3×5}、{2×3×7}、{2×5×7}、{3×5×7}、{2×3×5×7} 和 {1} 。

[这里有一个特殊的规定：1 表示无平方数]

但是，这只给出了 16 种构建无平方数 s 的方法，以及 100 种构建平方数 r^2 的方法。总的来说，我们只能构建 1600 = 16×100 个可能的数字。这是一个矛盾，因为我们需要构建 10000 个数字！因此，我们假设只有 4 个素数一定是错的。

在更抽象的证明中，包含着同样的思想，只是将数字替换成字母如 N 、root(N)（N 的平方根）、k 等等。关键思想保持不变：我们有数字 N 和 k 个素数。给定 N（例如，N=10,000），平方数 r^2 只有 root(N) 个选择（在我们的例子中，root(10000)=100 ），并且只有 2^k（在我们的例子中，2^k ）种构建无平方数的方法。这导致我们可以以 sr^2 形式构建的数字与我们知道可以构建的数字相比“太少”。(在我们的例子中，我们只能从 10000 个数字中构建 1600 个)。这是一个矛盾，因此我们假设存在有限多个素数一定是错误的。

证明

证明有点抽象，但是如果你已经看过上面的例子，希望你能够明白这些想法是从哪里来的！假设只有 k 个素数。现在考虑小于 N 的数字。构建平方数 r^2 的方法只有根号 N 种，因为 (root(N)+1)^2 ＞ N 。

但是，只有 2^k 种方法可以构建无平方数。(回想一下，当我们有 4 个素数时，我们可以构建 2^4 个无平方数：更一般地，对于 k 个素数，我们可以构建 2^k 个素数)。

这里为什么我们可以通过 k 个素数，构建 2^k 个无平方数呢？可以有一个组合学解释，事实上我们可以通过将 k 个素数中的一些相乘得到 n ，但对于同一个素数因子，我们要么选一次要么不选，因为我们一旦选两次，p^2 就成为 n 的一个因子，这样 n 就不是无平方数了。



在上图中我们将能够构建的数字的增长与根号 N 绑定在一起，而根号 N 的增长速度比 N 慢，在上图中红线代表我们能够构建的不同数字的数量，绿线代表我们必须构建的不同数字的数量，对于足够大的 N ，红线在绿线下方，这是一个矛盾，这是因为我们的假设只有 k 个素数的前提是错误的。

好了我们终于把这位才华横溢的数学家的证明给讲完了，我们下期见。



MathSpark