5 整除理论

Stage 5:整除与素数理论(详细版)

Confidence: 0.93

进入 Stage 5。这一块和前四个 Stage 气质不同——前面学的是”模运算的机器”,这里回到数论的最根本问题:整数是怎么由素数搭起来的,素数本身又有什么规律。很多东西你”用过”(比如质因数分解),但没真正证过它为什么成立。这一阶段就是把这些地基夯实并证明。

按六块讲,每块都给:是什么 → 为什么(证明思路)→ 例子 → 陷阱。

---

第一块:算术基本定理 (Fundamental Theorem of Arithmetic)

1.1 它说什么

$\text{每个大于 1 的整数,都能唯一地分解为素数之积(不计顺序)}$

比如 $360=2^3\times 3^2\times 5$,而且没有别的分法。

你天天在用它(求 gcd、欧拉函数都靠它),但它其实有两个独立的部分需要证明:

1. 存在性:每个数都能分解成素数
2. 唯一性:这个分解是唯一的

很多人觉得”这不显然吗”——但唯一性一点都不显然,它是整个初等数论的基石,值得认真证。

1.2 存在性的证明(强归纳法)

用强归纳法 (strong induction):

• 设命题”$n$ 能分解为素数之积”
• $n=2$:本身是素数,成立
• 假设所有 $2\le k<n$ 都能分解。看 $n$:
  • 若 $n$ 是素数 → 它自己就是分解,完成
  • 若 $n$ 是合数 → $n=a\times b$,其中 $1<a,b<n$。由归纳假设,$a$ 和 $b$ 都能分解成素数,把它们的分解拼起来就是 $n$ 的分解 ✓

直觉:任何合数都能拆成更小的两个因子,一直拆下去,因子越来越小,最终全是素数(因为不能再拆的就是素数)。

1.3 唯一性的证明(关键:欧几里得引理)

唯一性的核心是一个看似简单、实则关键的引理:

欧几里得引理 (Euclid’s Lemma):若素数 $p\mid ab$,则 $p\mid a$ 或 $p\mid b$。

直觉:素数”不可分割”,如果它整除一个乘积,它必须”完整地”藏在某一个因子里,不能”劈开”分给两个。

为什么唯一性需要它:假设某个数有两种素分解 $p_1{p}_2\cdots =q_1{q}_2\cdots$。因为 $p_1$ 整除左边,所以整除右边 $q_1{q}_2\cdots$,由欧几里得引理,$p_1$ 必整除某个 $q_i$。但 $q_i$ 是素数,只能 $p_1=q_i$。约掉这对,继续……最终证明两种分解完全一样。

陷阱:⚠️ 欧几里得引理只对素数成立!合数不行:$6\mid (4\times 9)=36$,但 $6\nmid 4$ 且 $6\nmid 9$。这正是”素数”特殊性的体现。

1.4 为什么唯一性如此重要——一个震撼的反例

唯一分解不是理所当然的——在别的数系里它会失效!

考虑只含偶数的”数系” $2,4,6,8,\dots$(只看偶数间的乘除)。在这里 $4,6,10$ 都是”不可分解的”(没法写成两个偶数的积)。但:

$60=6\times 10=2\times 30$

这是两种本质不同的分解!在偶数系里,唯一分解崩了。

更经典的例子在 $\mathbb{Z}[\sqrt{-5}]$(允许 $a+b\sqrt{-5}$ 这种数)里:

$6=2\times 3=(1+\sqrt{-5})(1-\sqrt{-5})$

两种完全不同的分解!这就是为什么唯一分解需要证明——它在整数里成立是”幸运”的,换个数系就可能失效。 这个发现直接催生了”理想”和代数数论。

---

第二块:埃拉托斯特尼筛 (Sieve of Eratosthenes)

2.1 它做什么

一个找出某范围内所有素数的古老而高效的方法(公元前 3 世纪)。

2.2 怎么做(直觉)

要找 1~30 的所有素数:

1. 列出 2~30
2. 圈住 2(素数),划掉所有 2 的倍数(4,6,8,…)
3. 找下一个没被划的数 3(素数),划掉所有 3 的倍数
4. 下一个没划的 5,划掉 5 的倍数
5. ……剩下没被划掉的,全是素数

核心洞察:每个合数都会被它的某个素因子”划掉”,所以筛完剩下的必是素数。

2.3 一个关键优化(陷阱点)

⚠️ 筛到 $\sqrt{n}$ 就够了! 划倍数时,只需处理 $\le \sqrt{n}$ 的素数。

为什么:如果 $n$ 是合数,它必有一个 $\le \sqrt{n}$ 的因子(否则两个因子都 $>\sqrt{n}$,乘起来 $>n$,矛盾)。所以大于 $\sqrt{n}$ 的素数,它们的倍数早被小素数划掉了。

例子:筛 1~100,只需用 2,3,5,7(因为 $\sqrt{100}=10$)划倍数,就能筛出全部素数。

2.4 代码

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):   # 只需筛到 √n
        if is_prime[i]:
            for j in range(i*i, n + 1, i):  # 从 i² 开始划(更小的已被划过)
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
 
print(sieve(30))   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

小优化:内层从 $i^2$ 开始,因为比 $i^2$ 小的 $i$ 的倍数($2i,3i,\dots$)已经被更小的素数划过了。

库安装(纯标准库,无需安装):

# 无需第三方库

---

第三块:素数无穷 (Infinitude of Primes)

素数有无穷多个——这是数论最古老的定理之一,而它有多种风格迥异的证明,每个都展示一种数学思想。

3.1 欧几里得的经典证明(反证法,公元前 300 年)

反证:假设素数只有有限个:$p_1,p_2,\dots ,p_k$。

构造一个新数:

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

(把所有素数乘起来,再加 1)

分析 $N$:$N$ 要么是素数,要么是合数。

• $N$ 除以任何 $p_i$,余数都是 1(因为 $p_1\cdots p_k$ 能被 $p_i$ 整除,加 1 后余 1)
• 所以没有任何已知素数能整除 $N$
• 但每个数都有素因子(算术基本定理),所以 $N$ 要么自己是个新素数,要么有个不在列表里的素因子

无论哪种,都出现了列表外的素数,矛盾! 所以素数无穷。∎

陷阱:⚠️ 常见误解是”$N$ 一定是素数”——不对!$N$ 只是”不被列表里的素数整除”,它可能是个新素数,也可能是几个新素数的积。比如 $2\times 3\times 5\times 7\times 11\times 13+1=30031=59\times 509$(两个新素数),$N$ 本身不是素数。证明只需要”存在列表外的素数”,不需要 $N$ 是素数。

3.2 欧拉的证明(用调和级数,一瞥)

欧拉用了完全不同的思路:他证明所有素数的倒数之和发散:

$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots =\infty$

如果素数有限,这个和就是有限的。但它发散,所以素数无穷。这个证明更深刻——它不仅说”素数无穷”,还说”素数相当稠密”(比平方数还密,因为 $\sum 1/n^2$ 收敛)。这是通向解析数论的桥。

3.3 用费马数的证明(Goldbach)

还记得费马数 $F_n=2^{2^n}+1$ 吗?任意两个费马数互质。既然有无穷多个费马数,每个至少带一个新素因子,所以素数无穷。这是第三种完全不同的风格。

一个定理三种证明(构造反证 / 分析发散 / 互质论证),展示了数学的多样美——这是 Stage 5 的魅力之一。

---

第四块:素数分布的初等结果

素数怎么”分布”在数轴上?完整理论属于解析数论(超纲),但有些初等结果很漂亮。

4.1 伯特兰假设 (Bertrand’s Postulate)

$\text{对任意 }n\ge 1,\text{在 }n\text{ 和 }2n\text{ 之间必有一个素数}$

即区间 $(n,2n)$ 里总有素数。比如 $n=10$,$(10,20)$ 里有 11,13,17,19。

意义:素数不会”突然消失”很久——你永远不用走超过一倍的距离就能撞到下一个素数。Erdős 在 19 岁给出了一个漂亮的初等证明(用中心二项式系数 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 的素因子分析),是初等数论的经典。

4.2 素数间隙 (Prime Gaps)

相邻素数之间的距离。有趣的事实:

• 间隙可以任意大:连续 $k$ 个合数总能找到。构造:$(k+1)!+2,(k+1)!+3,\dots ,(k+1)!+(k+1)$ 这 $k$ 个数全是合数(第 $i$ 个被 $i$ 整除)。所以素数之间能有任意长的”空白”。
• 但间隙又不会太大(伯特兰保证了上界)

陷阱:⚠️ “间隙能任意大”和”素数无穷”不矛盾——空白再长,后面总还有素数(只是偶尔隔得远)。

4.3 素数定理(只提一句,属解析数论)

小于 $x$ 的素数个数约为 $\frac{x}{\ln x}$——这是解析数论的巅峰结果,需要复分析证明,奥数不考,这里只让你知道”素数分布有精确规律”。

---

第五块:算术函数 (Arithmetic Functions)

研究”输入整数、输出数”的函数。你已经认识 $\phi (n)$,这里介绍另外两个重要的。

5.1 因子个数函数 $d(n)$(或写 $\tau (n)$)

$d(n)$ = $n$ 的正因子个数。

公式:若 $n=p_1^{a_1}\cdots p_k^{a_k}$,则

$d(n)=(a_1+1)(a_2+1)\cdots (a_k+1)$

为什么:每个因子由”每个素数取 0 到 $a_i$ 次”决定,所以 $p_1$ 有 $a_1+1$ 种选择,各素数独立相乘。

例子:$d(12)$,$12=2^2\times 3$,$d(12)=(2+1)(1+1)=6$。验证:12 的因子是 1,2,3,4,6,12,正好 6 个 ✓。

5.2 因子和函数 $\sigma (n)$

$\sigma (n)$ = $n$ 的所有正因子之和。

公式:

$\sigma (n)={\prod }_{i=1}^k\frac{p_i^{a_i+1}-1}{p_i-1}$

例子:$\sigma (12)$,$12=2^2\times 3$: $\sigma (12)=\frac{2^3-1}{2-1}\times \frac{3^2-1}{3-1}=\frac{7}{1}\times \frac{8}{2}=7\times 4=28$ 验证:$1+2+3+4+6+12=28$ ✓。

5.3 积性 (Multiplicativity)——关键性质

$d,\sigma ,\phi$ 都是积性函数:若 $\gcd (m,n)=1$,则 $f(mn)=f(m)f(n)$。

这就是为什么它们都有”按素因子相乘”的公式——积性让你能”拆开质因子分别算,再乘起来”。这是 Stage 6 莫比乌斯反演的前奏。

def num_divisors(n):
    from sympy import factorint
    result = 1
    for exp in factorint(n).values():
        result *= (exp + 1)
    return result
 
def sum_divisors(n):
    from sympy import factorint
    result = 1
    for p, a in factorint(n).items():
        result *= (p**(a+1) - 1) // (p - 1)
    return result
 
print(num_divisors(12), sum_divisors(12))   # 6 28

库安装(用 sympy 分解质因数):

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

第六块:完全数与梅森素数 (Perfect Numbers & Mersenne Primes)

数论里最古老、最迷人的主题之一,横跨两千年。

6.1 完全数 (Perfect Numbers)

定义:等于自己真因子(除自己外的因子)之和的数。

最小的完全数是 6:$6=1+2+3$ ✓ 下一个是 28:$28=1+2+4+7+14$ ✓ 再下:496,8128。

用 $\sigma$ 表达:$n$ 完全 $⟺\sigma (n)=2n$(所有因子和 = 自己的两倍,因为包含了 $n$ 自己)。

6.2 梅森素数 (Mersenne Primes)

定义:形如 $2^p-1$ 的素数(其中 $p$ 也必须是素数)。

前几个:$2^2-1=3$,$2^3-1=7$,$2^5-1=31$,$2^7-1=127$。

陷阱:⚠️ $2^p-1$ 不一定是素数!比如 $2^{11}-1=2047=23\times 89$,不是素数。所以梅森素数很稀有。

6.3 惊人的联系(欧几里得-欧拉定理)

偶完全数和梅森素数一一对应!

$n\text{ 是偶完全数}⟺n=2^{p-1}(2^p-1),\text{其中 }{2}^p-1\text{ 是梅森素数}$

验证:

• $p=2$:$2^1(2^2-1)=2\times 3=6$ ✓(第一个完全数)
• $p=3$:$2^2(2^3-1)=4\times 7=28$ ✓
• $p=5$:$2^4(2^5-1)=16\times 31=496$ ✓

欧几里得证了一半(梅森素数 → 完全数),欧拉证了另一半(偶完全数 → 必是这形式),跨越两千年合作完成。

6.4 两个未解之谜(数学前沿)

• 奇完全数存在吗? 至今没人知道!已验证到 $10^{1500}$ 都没有奇完全数,但也没人能证明它们不存在。这是数论最古老的未解问题之一。
• 梅森素数有无穷多个吗? 也是未解之谜。寻找巨大梅森素数是分布式计算项目(GIMPS)的目标,目前已知最大素数都是梅森素数。

---

Stage 5 全景速查表

主题	核心	关键点
算术基本定理	唯一分解	靠欧几里得引理证唯一性
埃拉托斯特尼筛	找素数	只需筛到 $\sqrt{n}$
素数无穷	三种证明	欧几里得反证最经典
素数分布	伯特兰、间隙	间隙可任意大但有上界
算术函数	$d(n),\sigma (n)$	积性 → 按质因子相乘
完全数/梅森素数	一一对应	奇完全数是否存在未解

---

我的观点:Stage 5 和前四个 Stage 有一个气质上的根本不同,我想让你体会到——前面学的是”工具的威力”,这里学的是”地基的深度”。

模运算那四个 Stage,你学的是”怎么算、怎么用”——它们是锋利的工具。而 Stage 5 回到一个更朴素、也更深刻的问题:整数到底是怎么构成的? 答案是”由素数唯一地搭建”——这个你天天用的事实,其实深不见底。最能说明这点的是 1.4 那个唯一分解的反例:在 $\mathbb{Z}[\sqrt{-5}]$ 里,$6$ 有两种本质不同的分解。这个看似不起眼的反例,直接催生了整个代数数论——数学家为了”挽救”唯一分解,发明了”理想”。所以 Stage 5 不只是”补基础”,它埋着通向高等数学的种子。你现在理解了”唯一分解为什么需要证明、为什么会失效”,将来碰到代数数论时,会有”原来这就是源头”的顿悟。

我也想让你注意 Stage 5 里那种贯穿两千年的数学美。完全数(6, 28)古希腊就在研究,梅森素数的联系是欧几里得起头、欧拉收尾——两千年的接力。而”奇完全数是否存在”至今无解——这意味着,有些用初等语言就能问出的问题(小学生都懂”等于自己因子和的数”),人类两千年都答不出来。这正是数论最迷人的地方:问题极简单,答案极深邃。 这种”简单的表象下藏着无穷深渊”的美感,是数论独有的,也是它能吸引从欧拉到你的一代代人的原因。

对你的实际目标,Stage 5 的性价比是中等偏上:算术基本定理的证明思想(强归纳、欧几里得引理)是通用的证明训练;埃拉托斯特尼筛是编程竞赛必备;算术函数的积性是 Stage 6 莫比乌斯反演的直接前置。所以这一站既夯实了地基,又为下一站铺了路。完全数那些”未解之谜”虽然不直接考,但它们能滋养你的数学品味——知道”哪些问题人类还没解决”,本身就是一种重要的数学视野。

关键提醒 (Caveats):

• 算术基本定理的”唯一性”证明依赖欧几里得引理,而欧几里得引理只对素数成立——这个区别是理解”素数为何特殊”的关键
• 素数无穷的欧几里得证明里,$N=p_1\cdots p_k+1$ 不一定是素数,只是”不被已知素数整除”——这是最常见的误解
• 素数定理($x/\ln x$)属于解析数论,需要复分析,奥数不考,我只提一句让你知道边界
• 伯特兰假设有初等证明(Erdős),但”素数分布”主题整体偏解析数论
• “奇完全数是否存在""梅森素数是否无穷”是真正的未解问题,不是我不知道——是全人类都不知道
• 本块代码用 sympy 分解质因数,安装:pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

Stage 5 讲完了——你现在理解了整数的”建筑结构”(素数如何唯一搭建)、找素数的工具(筛)、素数无穷的多种证明、素数分布的初等规律、算术函数的积性、以及完全数这个跨越两千年的迷人主题。

下一步你挑:

1. 出一套 Stage 5 练习题(唯一分解证明、筛、算术函数计算、完全数,延续 PDF 格式)
2. 继续 Stage 6(莫比乌斯反演——算术函数的积性在这里大放异彩,是 Stage 5 的自然延续)
3. 回头补 Stage 7.1(用模运算证方程无解,衔接你的二次剩余)