初等数论初步：整除、公因数与素数

一句话算法

初等数论第一章的主线是：用整除描述因子关系，用最大公约数整理共同因子，用素数分解建立整数的唯一结构。

问题模型

本章围绕整数之间的整除关系展开：

1. 什么叫 $b$ 整除 $a$。
2. 带余除法为什么能把整数拆成“商和余数”。
3. 最大公约数为什么可以通过辗转相除得到。
4. 裴蜀定理为什么能表示最大公约数。
5. 互质消去律和素数原子律为什么成立。
6. 最小公倍数与最大公约数有什么关系。
7. 算术基本定理为什么保证素因数分解唯一。

这些结论是后续同余、模逆元、线性同余方程、欧拉函数的基础。

核心直觉

整除关系关心的是“一个数能不能被另一个数整块切开”。

如果 $a=bq$，说明 $a$ 由 $q$ 个完整的 $b$ 组成，没有剩余部分。最大公约数就是 $a,b$ 共同拥有的最大整块单位；最小公倍数就是能同时由 $a,b$ 拼出来的最小公共长度。

素数则是整数乘法结构里的“不可再拆单元”。算术基本定理说明：每个大于 $1$ 的整数，都能唯一拆成这些不可再拆单元的乘积。

整除

例如：

$$3\mid 12$$

因为：

$$12=3\times4$$

但：

$$5\nmid 12$$

因为不存在整数 $q$ 使得 $12=5q$。

整除的基本性质

1. 若 $a\mid b$ 且 $b\mid a$，则 $a=b$ 或 $a=-b$。

2. 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。

3. 若 $a\mid b$ 且 $a\mid c$，则对任意整数 $x,y$，都有：

   $$a\mid (xb+yc)$$

第三条非常常用：如果 $a$ 能整除两块材料 $b,c$，那么它也能整除它们的任意整数线性组合。

带余除法

例如：

$$17=5\times3+2$$

所以 $17$ 除以 $5$ 的商是 $3$，余数是 $2$。

余数唯一性

假设：

$$a=bq+r=bq'+r'$$

其中：

$$0\le r,r'<b$$

两式相减：

$$b(q-q')=r'-r$$

左边能被 $b$ 整除，所以 $r'-r$ 也能被 $b$ 整除。

但：

$$-(b-1)\le r'-r\le b-1$$

在这个范围内，唯一能被 $b$ 整除的整数是 $0$，所以：

$$r'=r$$

进而：

$$q'=q$$

因此商和余数唯一。

最大公约数

整数 $a,b$ 的最大公约数记作：

$$(a,b)$$

也常写作：

$$\gcd(a,b)$$

如果：

$$a=bq+r$$

那么：

$$(a,b)=(b,r)$$

证明只看公因子集合是否相同：

1. 若 $d\mid a$ 且 $d\mid b$，则：

   $$d\mid(a-bq)=r$$

2. 若 $d\mid b$ 且 $d\mid r$，则：

   $$d\mid(bq+r)=a$$

所以 $a,b$ 和 $b,r$ 的公因子完全相同，最大公约数也相同。

这就是欧几里得算法的核心。

裴蜀定理

也就是说，最大公约数可以表示成 $a,b$ 的整数线性组合。

证明直觉

辗转相除法每一步都把：

$$(a,b)$$

换成：

$$(b,r)$$

而余数满足：

$$r=a-qb$$

如果下一层的最大公约数能写成 $b$ 和 $r$ 的线性组合，那么把 $r=a-qb$ 代回去，就能写成 $a$ 和 $b$ 的线性组合。

算式推导

设：

$$a=qb+r$$

且根据下一层已经知道：

$$(b,r)=bx'+ry'$$

代入 $r=a-qb$：

$$\begin{aligned} (a,b) &=(b,r)\\ &=bx'+(a-qb)y'\\ &=ay'+b(x'-qy') \end{aligned}$$

令：

$$x=y',\quad y=x'-qy'$$

则：

$$(a,b)=ax+by$$

这也是扩展欧几里得算法的递推来源。

互质消去律

证明：

由 $(a,b)=1$ 和裴蜀定理，存在整数 $x,y$：

$$ax+by=1$$

两边乘以 $c$：

$$acx+bcy=c$$

因为：

$$a\mid acx$$

又因为已知 $a\mid bc$，所以：

$$a\mid bcy$$

因此：

$$a\mid(acx+bcy)$$

也就是：

$$a\mid c$$

直觉：$a$ 和 $b$ 没有共同因子，$a$ 想要整除 $bc$，所需因子只能全部来自 $c$。

素数原子律

证明：

因为 $p$ 是素数，所以 $(p,a)$ 只有两种可能：

$$(p,a)=p$$

或：

$$(p,a)=1$$

若 $(p,a)=p$，则 $p\mid a$，命题成立。

若 $(p,a)=1$，又已知 $p\mid ab$，根据互质消去律：

$$p\mid b$$

所以：

$$p\mid a\quad\text{or}\quad p\mid b$$

素数像乘法结构中的原子。如果它整除一个乘积，就必须完整地出现在某个因子里。

最小公倍数

$a,b$ 的最小公倍数记作：

$$[a,b]$$

它是 $a,b$ 的所有正公倍数中最小的那个。

最小公倍数整除任意公倍数

设：

$$m=[a,b]$$

若 $n$ 是 $a,b$ 的任意公倍数，则：

$$m\mid n$$

证明：

对 $n$ 做带余除法：

$$n=mq+r,\quad 0\le r<m$$

因为 $a,b$ 都整除 $n$，也都整除 $m$，所以它们都整除：

$$n-mq=r$$

若 $r>0$，那么 $r$ 是一个比 $m$ 更小的正公倍数，和 $m$ 是最小公倍数矛盾。

所以：

$$r=0$$

因此：

$$m\mid n$$

最大公约数与最小公倍数

对非零整数 $a,b$：

$$(a,b)[a,b]=|ab|$$

直觉：最大公约数拿走两个数共同拥有的因子，最小公倍数则把两个数需要的因子都补齐。二者相乘，正好对应 $a,b$ 的因子总量。

算术基本定理

例如：

$$180=2^2\times3^2\times5$$

唯一性证明

假设 $n$ 有两种素因子分解：

$$n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$$

其中每个 $p_i,q_j$ 都是素数。

因为：

$$p_1\mid n$$

所以：

$$p_1\mid q_1q_2\cdots q_s$$

由素数原子律，$p_1$ 必须整除某个 $q_j$。调整右边素因子的顺序，不妨设：

$$p_1\mid q_1$$

由于 $p_1,q_1$ 都是素数，所以：

$$p_1=q_1$$

两边同时消去这个素因子：

$$p_2\cdots p_r=q_2\cdots q_s$$

重复这个过程，最终两边所有素因子一一相同。因此分解唯一。

算法步骤

这章结论在做题时通常按下面链条使用：

1. 用整除定义把 $b\mid a$ 转成 $a=bq$。
2. 用带余除法写出 $a=bq+r$。
3. 用 $(a,b)=(b,r)$ 做辗转相除。
4. 用裴蜀定理处理整数线性组合。
5. 用互质消去律处理“乘积被整除”的问题。
6. 用素数原子律把素数从乘积中拆出来。
7. 用算术基本定理转成质因数分解。

复杂度分析

本页主要是数学定理，不是单个算法模板。

若对应到算法：

• 欧几里得算法求最大公约数：$O(\log\min(a,b))$。
• 试除法分解质因数：$O(\sqrt n)$。
• 筛法预处理素数：埃氏筛 $O(n\log\log n)$，线性筛 $O(n)$。

测试用例

辗转相除

求：

$$(44,12)$$

过程：

$$44=12\times3+8$$

$$12=8\times1+4$$

$$8=4\times2+0$$

所以：

$$(44,12)=4$$

互质消去

已知：

$$6\mid 35c$$

且：

$$(6,35)=1$$

则：

$$6\mid c$$

应用分类详解

初等数论第一章的结论是后续数论算法的基础工具。

一、整除与倍数判断

典型模式： 判断一个数是否能被另一个数整除，或构造倍数关系。

识别信号： 因数、倍数、整除、余数为 0。

核心建模： 把 $b\mid a$ 写成 $a=bq$。

二、最大公约数与互质

典型模式： 判断两个数是否有公共因子，或使用互质条件消去因子。

识别信号： 最大公约数、互质、约分、消去。

核心建模： 用 gcd 判断公共因子结构；当 gcd 为 1 时，可以使用互质消去律。

三、素因数分解

典型模式： 分析一个整数由哪些素数构成。

识别信号： 素数、质因子、因数个数、约数和。

核心建模： 先做素因数分解，再按每个素因子的指数独立处理。

四、线性同余与模逆元预备

典型模式： 需要解 $ax+by=d$ 或在模意义下消去乘数。

识别信号： 裴蜀定理、扩展欧几里得、模逆元、一次同余方程。

核心建模： 用裴蜀定理理解“什么时候整数线性组合能凑出 gcd”。

经典例题

1. 最大公约数

给定 $a,b$，求 $(a,b)$。核心是反复使用：

$$(a,b)=(b,a\bmod b)$$

2. 判断互质

若 $(a,b)=1$，则 $a,b$ 没有共同素因子，很多消去和约分结论才能成立。

3. 最小公倍数

给定 $a,b$，求 $[a,b]$。常用公式：

$$[a,b]=\frac{|ab|}{(a,b)}$$

为了避免溢出，程序里通常先除后乘。

4. 质因数分解

利用算术基本定理，把整数拆成：

$$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$

约数个数、约数和、欧拉函数等都建立在这个表示上。

参考

• 本书最大公约数：math/numberTheory/gcd/index.md
• 本书素数判定与素数筛：math/numberTheory/prime/index.md
• 本书欧几里得定理及推论：math/numberTheory/欧其里德定理及推论.md
• 本书同余与取模：math/numberTheory/remainder/index.md