素数

引入

为什么 $1$ 不算素数？

素数有无穷多个，这个结论两千多年前就被证明了，它需要什么前提？

素数的分布看起来毫无规律，为什么还会有一个”定理”描述它？

正文

定义

设 $p$ 是除 $0$ 和 $\pm 1$ 外的整数，如果 $p$ 除了 $\pm 1$ 和 $\pm p$ 外没有其他约数，则称 $p$ 为素数（也称质数）。大于 $1$ 且不是素数的整数称为合数。

为什么 $1$ 不是素数

若 $1$ 是素数，唯一分解定理就会失效：$6=2\times 3=1\times 2\times 3=1\times 1\times 2\times 3$，分解方式无穷多。

把 $1$ 排除在外，是为了保证分解的唯一性。这是定义的选择，不是发现。

数	类型	原因
$-3$	素数（按上述定义）	约数只有 $\pm 1,\pm 3$
$1$	既非素数也非合数	排除以保唯一性
$0$	不讨论	任何数都整除 $0$
$2$	唯一的偶素数

素数有无穷多个

定理（欧几里得）

素数有无穷多个。

证明（反证法）：

假设素数只有有限个，记为 $p_1,p_2,\cdots ,p_n$。构造

$N=p_1{p}_2\cdots p_n+1$

则 $N$ 除以任一 $p_i$ 都余 $1$，所以 $p_1,\cdots ,p_n$ 都不整除 $N$。

但 $N>1$，必有素因数。这个素因数不在假设的列表中，矛盾。故素数有无穷多个。

证明的关键：构造一个”躲开所有已知素数”的数。这个技巧在数论中反复出现。

唯一分解定理

定理（算术基本定理）

设 $n$ 是大于 $1$ 的正整数，则 $n$ 可以表示为有限个素数的乘积，且在不计次序的意义下表示唯一： $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ 其中 $p_1<p_2<\cdots <p_k$ 为素数，${\alpha }_i$ 为正整数。

唯一性为什么重要：它保证了”分解”这件事有意义。若分解不唯一，”$n$ 的素因数”就无法定义。

素数定理

${\lim }_{n\to \infty }\frac{\pi (n)}{n/\ln n}=1$

其中 $\pi (n)$ 表示不超过 $n$ 的素数个数。

含义：$\pi (n)$ 大约等于 $\frac{n}{\ln n}$。素数虽然有无穷多个，但密度趋于零。

即对于较小的 $n$，近似公式 $n/\ln n$ 也相当精确。例如当 $n=10^9$ 时，误差不超过 $6\%$：

量	值
实际 $\pi (10^9)$	$50,847,534$
近似 $10^9/\ln 10^9$	$48,254,942$

素数判定

方法	做法	复杂度
试除法	用 $\le \sqrt{n}$ 的素数试除	$O(\sqrt{n})$
埃拉托斯特尼筛法	筛去合数，留下素数	$O(n\log \log n)$
米勒-拉宾	概率判定	$O(k{\log }^{3}n)$
AKS	确定性多项式算法	$O({\log }^{6}n)$

试除只需到 $\sqrt{n}$：若 $n=ab$ 且 $a\le b$，则 $a\le \sqrt{n}$，所以只需检查较小的因子。

与密码学的关系

RSA 加密的基础是：大整数分解很难，但验证乘积很容易。

操作	难度
两个大素数相乘	容易
把乘积分解回两个素数	极难

素数定理在这里的意义：它保证了”大素数足够多”，可以随时生成新的密钥。

常见误区

错误说法	问题
”$1$ 是素数”	会破坏唯一分解
”$2$ 不是素数”	是唯一的偶素数
”素数有有限个”	欧几里得已证无穷
”素数定理给出了精确个数”	是渐近估计
”所有奇数都是素数”	$9$、$15$ 是反例

引出

为什么排除 $1$ 才能保证唯一分解？

素数定理的证明需要什么工具？为什么它属于解析数论？

是否存在无穷多对孪生素数？

• 数学归纳法：唯一分解定理的证明工具
• 集合：素数集的描述
• 坐标变换：数论中的变换思想
• 数学基础：数学基础的整体框架
• 数学：数学学科入口