质数/素数

本文旨在剖析质数的性质，不会涉及到如何判定素数以及素数相关的筛。

质数的定义

质数的朴素定义是：

一个大于 1 的整数 \(p\)，如果它的正因数只有 \(1\) 和它本身，则称 \(p\) 是一个质数（\(\text{prime}\)）。 否则，称它是合数（\(\text{composite}\)）。

比如：

• \(2,3,5,7,11,13,\dots\) 是质数；
• \(4 = 2 \times 2, 6 = 2 \times 3, 12 = 3 \times 4\) 都是合数。

值得注意的事情是：

• \(1\) 不是质数也不是合数，一般单独作为「单位元」（unit）看待。
• \(0\) 不在讨论范围内，这些性质通常只对正整数才有意义。

质数的不可分性

根据质数的定义，我们可以非常简单得到一个结论「质数不能被拆成两个更小的因数」。

那么在更加形式化的说法下，我们称下面两件事是等价的：

1. \(p\) 是质数；
2. 假设 \(p > 1\)，对任意整数 \(a,b\)，若 \(p\mid ab\)，则 \(p\mid a\) 或 \(p\mid b\)（即 \(p\) 整除乘积就必整除某个因子）

质数的这个性质我暂时没有在任何资料中找到准确的名字， 我们暂且称之为「不可分性」。

请注意，我使用「不可分性」是为了在本文中明确指明这个性质， 防止出现「前文的性质」类似的措辞。在与他人交流时请完整表述出具体性质， 不要引起歧义。

「不可分性」是质数非常关键的性质，我们下文会多次提到。

我们对「不可分性」进行一个小总结：

对质数 \(p\)，不允许出现 \(p\mid ab\)，但 \(p\) 藏在\(a\) 一点、\(b\) 一点里， 导致 \(a,b\) 自己都不是 \(p\) 的倍数。 必须有至少一个因子本身就是 \(p\) 的倍数。

顺带一提，在整数环 \(\mathbb Z\) 中，只能分解出平凡因子（不可约）与这种性质是等价的。

不可分性等价关系的证明

2到1的证明

假设 \(p>1\) 且满足 \(p\mid ab \Rightarrow p\mid a\) 或 \(p\mid b\)。

如果 \(p\) 不是质数，那它可以写成 \(p=ab\)，其中 \(1<a,b<p\)。

显然 \(p\mid ab\)，按照性质，要么 \(p\mid a\) 要么 \(p\mid b\)，但这不可能（因为 \(a,b\) 都比 \(p\) 小）。

得到矛盾，说明假设错误，只能是 \(p\) 是质数。

接下来我们尝试从 \(1\) 的角度去证明 \(2\)。

1到2的证明

这部分的证明相对来说比较困难。 我们分两种情况讨论：

情况 A：\(p \mid a\)

那就直接满足 \(p\mid a\) 或 \(p\mid b\) ，结束。

情况 B：\(p \nmid a\)

这时候要证明：\(p\mid b\) 必然成立。

所以关键问题变成：

已知 \(p\) 是质数，\(p\mid ab\)，且 \(p\nmid a\)，如何推出 \(p\mid b\) ？

首先我们需要先分析一下 \(\gcd(a,p)\)。 由于 \(p\) 是质数，它的正因数只有 \(1\) 和 \(p\)。 \(\gcd(a,p)\) 是 \(p\) 的一个正因数，所以只能是 \(1\) 或 \(p\)。 又因为假设了 \(p\nmid a\)，所以不可能 \(\gcd(a,p)=p\)。 因此只剩下 \(\gcd(a,p) = 1\)

这里我们可以应用「裴蜀定理」，既然 \(\gcd(a,p) = 1\)，那么一定存在整数 \(x,y\) 使得 \(ax+py = 1\)。 我们对这个式子两边同时乘 \(b\)，可得到 \(abx+pby=b\)。

已知 \(p\mid ab\)，所以 \(p\mid abx\)（因为 \(abx = (ab)\cdot x\)），同时显然 \(p\mid pby\)； 因此左边的 \(abx + pby\) 是两个被 \(p\) 整除的数之和，仍被 \(p\) 整除，所以 \(p \mid abx + pby\)。 而 \(abx+pby\) 正好等于右边的 \(b\)，于是我们得到 \(p \mid b\)。

\(\text{Q.E.D.}\)

用唯一分解定理证明不可分性

上面我们用裴蜀定理证明了：若 \(p\) 是质数，且 \(p\mid ab\)，则 \(p\mid a\) 或 \(p\mid b\)。 其实还有一种非常直观的证明，前提是我们已经接受了「唯一分解定理」。

设 \(p\) 是质数，且 \(p\mid ab\)。由于每个正整数的质因子分解是唯一的，可以写

\[ a = \prod_i q_i^{\alpha_i}, \ \ b = \prod_j r_j^{\beta_j}, \ \ ab = \prod_i q_i^{\alpha_i} \prod_j r_j^{\beta_j} \]

又因为 \(p\mid ab\)，所以 \(ab\) 的质因子分解中必然出现了质数 \(p\)。这个因子要么来自 \(a\) 的分解，要么来自 \(b\) 的分解：

若 \(p\) 是某个 \(q_i\)，则 \(p\mid a\)；若 \(p\) 是某个 \(r_j\)，则 \(p\mid b\)。 于是得到 \(p\mid ab \Rightarrow p\mid a\) 或 \(p\mid b\)。

不过值得注意的事情是，唯一分解定理的证明本身就依赖这个整除性质， 所以如果采用这种证明方式，就不能反过来用唯一分解定理作为前提，否则会形成逻辑循环。 在本文中，我们是先用裴蜀定理证明该性质，再用它证明唯一分解定理的唯一性。

算数基本定理/唯一分解定理

定义

对于任意整数 \(n>1\)，可以写成：

\[ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \]

其中 \(p_i\) 都是质数，\(a_i\) 都是正整数。并且这种分解方式在忽略质数因子的顺序后是唯一的。

也就是说，任何大于 1 的整数都可以拆解成质数的幂的乘积，而且拆的方式是唯一的。

存在性证明

大致思路：

对 \(n\) 做数学归纳；

如果 \(n\) 本身是质数，就不用分解；

如果是合数，就能写成 \(n = ab\)，且 \(1<a,b<n\)；

用归纳假设，把 \(a,b\) 分别分解为质数乘积；

把这些质数合起来，就是 \(n\) 的质因子分解。

事实上，只要有“质数”这个概念，就可以递归地把任何整数分解到底。

唯一性证明

唯一性的经典证明依赖于前文提到的「不可分性」。

假设存在两个不同的分解：

\[ n = p_1 p_2\cdots p_k = q_1 q_2 \cdots q_l \]

其中 \(p_i,q_j\) 都是质数。取 \(p_1\)，它整除右边的乘积 \(q_1\cdots q_\ell\)；利用不可分性， 必然有 \(p_1\mid q_j\) 对某个 \(j\) 成立，但 \(q_j\) 本身就是质数，所以 \(p_1=q_j\)。 把这对相同的质数因子两边同时约掉，得到一个更短的等式。 重复这个过程，最终说明两边的质数列表一样，只是顺序不同。

质数是无穷多的吗？

欧几里得证明

假设质数只有有限多个：\(p_1,p_2,\dots,p_k\)；

构造一个新的数：

\[ N = p_1 p_2 \cdots p_k + 1 \]

对于任意一个 \(p_i\)，有

\[ N \equiv 1 \pmod p_i \]

所以 \(p_i\nmid N\)。

但 \(N>1\)，所以 \(N\) 或者本身是质数，或者有某个质因子。 无论哪种情况，都得到一个不在 \({p_1,\dots,p_k}\) 中的新质数，矛盾。

这类构造的核心思想是，把所有已知质数乘起来再加 \(1\)， 强行制造一个与所有已知质数互不整除的新数，从而逼出新的质因子。

Euler 的无穷积

\(\text{Euler}\) 发现，可以把

\[ \sum_{n=1}^{\infty} \frac{1}{n} \]

这个调和级数改写成关于质数的无穷乘积：

\[ \sum_{n=1}^{\infty} \frac{1}{n} = \prod_{p\ prime} \frac{1}{1 - p^{-1}} \]

直观来说：

\(\displaystyle\frac{1}{1-p^{-1}} = 1 + \frac{1}{p} + \frac{1}{p^2}+\cdots\)

把所有质数的这种几何级数乘起来，会把所有整数的倒数都“展开”出来。

因为左边的调和级数是发散的，所以右边对应的无穷乘积也不能收敛，这在某种意义上也说明了质数不能只有有限个。 否则右边是有限个因子的乘积，就只是一串常数了。

质数的分布

定义：

\[ \pi(x) = 不超过\ x\ 的质数个数 \]

比如：

• \(\pi(10)=4\)（质数 \(2,3,5,7\)）；
• \(\pi(100)=25\)；
• \(\pi(1000)=168\)。

直观上，质数越来越稀疏：比如在 \([1,10]\) 中有 4 个，在 \([1,1000]\) 中平均每 6 个数里才有一个质数。 但另一方面， 质数又总是会继续出现， 同时也没有人能找到一个「从某个地方开始就再也没有质数」的界。

质数定理

当 \(x\to\infty\) 时，

\[ \pi(x) \sim \frac{x}{\ln x} \]

即

\[ \lim_{x\to \infty} \frac{\pi(x)}{x/ {\ln (x)}} = 1 \]

直观含义就是大约每 \(\ln x\) 个整数中有一个质数， 在数量级 \(10^6\) 左右，\(\ln 10^6 \approx 13.8\)，表示平均 \(14\) 个数里有一个质数左右。

更进一步的结果会给出误差项，误差的精细控制与著名的黎曼猜想直接相关——这是现代数论中最核心也最困难的未解难题之一。

一些关于质数的未解决问题

孪生素数猜想

有无穷多对质数 \((p,p+2)\)？比如 \((3,5),(5,7),(11,13),(17,19),\dots\)。

这个问题在形式上非常简单，但至今无人证明。

目前只能证明：质数之间距离为某个常数的“无穷多次发生”很难保证。

强哥德巴赫猜想

任意足够大的偶数都可以表示成两个质数之和。

比如：

• \(10=3+7\)
• \(100=47+53\)
• \(2024=1013+1011\)

计算机已经验证了极大范围内都成立，但完整的数学证明依然缺失。

黎曼猜想

黎曼猜想从表面上看是关于黎曼 \(\zeta\) 函数零点分布的分析问题， 但实际上它与质数分布的误差有很强的关联：若黎曼猜想成立，那么质数定理中的误差会大大收敛，能够让我们更好地描述素数的分布。

这些问题都在告诉我们：质数的分布既不完全随机，也远远谈不上简单有序，正是这种「暧昧的状态」成就了数论的魅力。

日志

本页面创建于 2025/12/11 14:51