整除与素数

参考资料

• 整除 - 维基百科
• 素数 - 维基百科
• 最大公约数 - OI Wiki
• 筛法 - OI Wiki

引入

整除（Divisibility）是数论一切性质的起点：从素数分布、最大公约数到费马小定理，最底层都是在问一句话——「$a$ 能不能整除 $b$」。

整数和有理数不一样。有理数里除法总能做，$3$ 除以 $7$ 就是 $\frac{3}{7}$，没什么可说的。但在整数的世界里，除法常常「除不尽」，余下一个尾巴。正是这个「尾巴」——余数——撑起了整个初等数论。我们先把整除这件事讲清楚，再一步步推到带余除法、最大公约数，最后到算术基本定理这块「基石」。

整除

定义

整数 $a,b$（$a\ne 0$），若存在整数 $q$ 使 $b=aq$，称 $a$ 整除 $b$，记为：

$$a\mid b$$

这时也说 $a$ 是 $b$ 的 因子（约数），$b$ 是 $a$ 的 倍数。若不存在这样的 $q$，记 $a\nmid b$。

注意竖线 $\mid$ 是一个 关系（成立或不成立），不是分数线 $\frac{b}{a}$（一个数值）。$a\mid b$ 读作「$a$ 整除 $b$」，方向是「小的整除大的」。

性质

下面这些性质看起来朴素，却是后面所有推导反复用到的「积木」。

性质	描述
传递性	$a\mid b,\,b\mid c\Rightarrow a\mid c$
线性组合	$a\mid b,\,a\mid c\Rightarrow a\mid(bx+cy)$
整除积	$a\mid b\Rightarrow a\mid bc$
同号大小	$a\mid b,\,b\ne 0\Rightarrow\lvert a\rvert\le\lvert b\rvert$
反对称	$a\mid b,\,b\mid a\Rightarrow a=\pm b$
缩放不变	$a\mid b\iff ka\mid kb\,(k\ne 0)$

提示

「线性组合」这条是日常做题用得最多的。它的意思是：只要 $a$ 同时整除两个数，那么这两个数怎么加权拼起来（系数还得是整数），$a$ 照样整除。比如 $3\mid 6$、$3\mid 9$，那么 $3$ 自然整除 $6\cdot 5-9\cdot 2=12$。很多「证某式被某数整除」的题，本质都是把目标式凑成已知整除项的线性组合。

特别约定：任何整数都整除 $0$（取 $q=0$ 即可），而 $0$ 只整除 $0$。$1$ 和 $-1$ 整除一切整数。

整除证明小题

整除类证明题的两条常用思路：凑线性组合，或 按余数分类讨论（即对模一个小数 $m$ 把变量分成 $m$ 种情况逐一验证）。

例：证 $6\mid n^3-n$。先因式分解 $n^3-n=(n-1)\,n\,(n+1)$，这是三个 连续整数 的积。连续三个整数里必有一个是 $2$ 的倍数、必有一个是 $3$ 的倍数，故同时被 $2$ 和 $3$ 整除；又 $\gcd(2,3)=1$，于是被 $2\cdot 3=6$ 整除。一般地，连续 $k$ 个整数的积必被 $k!$ 整除。

例：证 $9\mid 4^n+15n-1$（$n\ge 0$）。用对 $n$ 的归纳。$n=0$ 时 $4^0+0-1=0$，$9\mid 0$ 成立。设 $9\mid 4^n+15n-1$，看相邻两项之差：

$$\begin{aligned} \bigl(4^{n+1}+15(n+1)-1\bigr)-\bigl(4^n+15n-1\bigr) &=4^{n+1}-4^n+15 \\ &=3\cdot 4^n+15 \\ &=3\,(4^n+5) \end{aligned}$$

而 $4\equiv 1\pmod 3$ 故 $4^n\equiv 1$，得 $4^n+5\equiv 0\pmod 3$，即 $3\mid(4^n+5)$，于是差被 $9$ 整除。差与前一项都被 $9$ 整除，二者之和也被 $9$ 整除，归纳完成。

例：证 $7\mid 2^{2n+1}+3^{2n+1}+\cdots$ 一类式子时，用同余更省事。如证 $7\mid 3^{2n}-2^n$：$3^2=9\equiv 2\pmod 7$，故 $3^{2n}=(3^2)^n\equiv 2^n\pmod 7$，于是 $3^{2n}-2^n\equiv 0\pmod 7$。先化同底、再比对，是这类题的标准动作。

带余除法

对任意整数 $a$ 与正整数 $b$，存在 唯一 的一对整数 $q,r$ 使：

$$a=bq+r,\quad 0\le r<b$$

$q$ 称为 商，$r$ 称为 余数。这就是 带余除法（Division with Remainder），也叫欧几里得除法。

直觉上，它说的是「把 $a$ 放到数轴上，找它落在哪两个相邻的 $b$ 的倍数之间」：$q$ 是那个倍数的编号，$r$ 是从倍数到 $a$ 还差多远。商 $q=\lfloor a/b\rfloor$ 向下取整，余数 $r=a-b\lfloor a/b\rfloor$。

「存在且唯一」这两点都要紧。存在性保证总能除；唯一性保证余数是被良好定义的——它正是后面 同余 里「模 $b$」的那个余数。带余除法也是欧几里得算法的引擎。

提示

余数被规定为 非负。所以 $-7$ 除以 $3$，商是 $-3$、余数是 $2$（因为 $-7=3\times(-3)+2$），而不是商 $-2$、余数 $-1$。编程里 % 对负数的行为各语言不同，手算时认准「$0\le r<b$」这条就不会错。

最大公约数

定义

整数 $a,b$ 不全为 $0$，最大的同时整除 $a,b$ 的正整数称为 最大公约数（Greatest Common Divisor，GCD），记为：

$$\gcd(a,b)\quad\text{或}\quad (a,b)$$

若 $\gcd(a,b)=1$，称 $a,b$ 互素（Coprime），意思是它们除了 $1$ 没有别的公因子。互素是数论里极其重要的条件——欧拉定理、CRT、积性函数处处都要求互素。

类似地可定义多个数的 $\gcd(a_1,\dots,a_n)$，它等于把这些数的公因子取到最大。

欧几里得算法

求 $\gcd$ 的标准方法是 欧几里得算法（辗转相除法），它基于一条关键恒等式：

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

为什么这条成立？设 $a=bq+r$。任何同时整除 $a,b$ 的数，由「线性组合」必然整除 $r=a-bq$；反过来任何同时整除 $b,r$ 的数也整除 $a=bq+r$。所以 $\set{a,b}$ 的公因子集合和 $\set{b,r}$ 的公因子集合 完全一样，最大的那个自然也相等。于是问题从 $(a,b)$ 缩小成更小的 $(b,r)$，反复做下去，余数严格递减，最终必然减到 $0$：

$$\begin{aligned} \gcd(252,105)&=\gcd(105,42) \\ &=\gcd(42,21) \\ &=\gcd(21,0)=21 \end{aligned}$$

当一个数变成 $0$ 时，另一个数就是答案（因为 $\gcd(g,0)=g$）。每做一步，较大数至少减半（可以证明两步之内余数减半），所以复杂度为 $O(\log\min(a,b))$，飞快。

例：求 $\gcd(1071,462)$，把每一步的带余除法写全：

$$\begin{aligned} 1071&=2\times 462+147 \\ 462&=3\times 147+21 \\ 147&=7\times 21+0 \end{aligned}$$

余数依次为 $147,21,0$，最后一个非零余数 $21$ 就是答案，$\gcd(1071,462)=21$。可以验算 $1071=21\times 51$、$462=21\times 22$，且 $\gcd(51,22)=1$，确实约干净了。

提示

手算时把每一步写成「被除数 $=$ 商 $\times$ 除数 $+$ 余数」的固定格式，下一行的除数和余数就是这一行的除数和余数——「除数顶上去当被除数，余数顶上去当除数」，照着滚就不会乱。余数严格递减保证几步内必然落到 $0$。

裴蜀定理

对任意不全为 $0$ 的整数 $a,b$，存在整数 $x,y$ 使：

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

这就是 裴蜀定理（Bézout's Identity）。它的分量很重：它说 $\gcd(a,b)$ 不只是「最大的公因子」，还是「$a,b$ 能凑出的最小正整数」。凡是形如 $ax+by$（$x,y$ 取遍整数）的数，恰好就是 $\gcd(a,b)$ 的所有倍数，一个不多、一个不少。

系数 $x,y$ 可由 扩展欧几里得算法（Extended Euclidean Algorithm）求出——在辗转相除回溯的过程中顺带把系数也算回来。它是求 模逆元 和解 一次不定方程 的核心工具。

例：求一组整数 $x,y$ 使 $1071x+462y=21$。先做辗转相除（上面已算过），再 从下往上逐步回代，把每一行的余数表示成 $1071,462$ 的线性组合：

$$\begin{aligned} 21&=462-3\times 147 \\ &=462-3\times(1071-2\times 462) \\ &=462-3\times 1071+6\times 462 \\ &=7\times 462-3\times 1071 \end{aligned}$$

第一行来自 $462=3\times 147+21$，把 $147=1071-2\times 462$ 代进去，合并同类项即得 $1071\times(-3)+462\times 7=21$。所以 $(x,y)=(-3,7)$，验算 $1071\times(-3)+462\times 7=-3213+3234=21$，正确。

提示

回代的诀窍是 每次只代换最近一次出现的余数，并始终把式子整理成「$\square\times 1071+\square\times 462$」的两项形式，不要急着乘开成具体数字，否则系数容易抄错。代码实现里不必真的回代，而是用递推关系 $x=y',\,y=x'-\lfloor a/b\rfloor\,y'$ 在递归返回时同步更新，一趟搞定。

推论（也常单独叫裴蜀定理）：

$$ax+by=c\ \text{有整数解}\iff\gcd(a,b)\mid c$$

最小公倍数

同时是 $a,b$ 倍数的最小正整数，称为 最小公倍数（Least Common Multiple，LCM），记 $\operatorname{lcm}(a,b)$ 或 $[a,b]$。

它和 $\gcd$ 有一条优美的对偶关系：

$$\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|$$

所以实际计算时，先用欧几里得算法求出 $\gcd$，再用 $\operatorname{lcm}(a,b)=|ab|/\gcd(a,b)$ 得到 $\operatorname{lcm}$（先除后乘可避免溢出）。

例：求 $\operatorname{lcm}(1071,462)$。已知 $\gcd=21$，故

$$\operatorname{lcm}(1071,462)=\frac{1071\times 462}{21}=1071\times 22=23562$$

写成 $\dfrac{1071}{21}\times 462=51\times 462$ 先约后乘，能避开中途的大数。

提示

为什么是「乘积 $=ab$」而不是「和」之类？看素因子就懂了：对每个素数 $p$，$\gcd$ 取 $a,b$ 两边指数的较小值，$\operatorname{lcm}$ 取较大值，「较小 $+$ 较大 $=$ 两者之和」，正好拼回 $ab$ 在 $p$ 上的指数。下一节的唯一分解会把这件事说得更透。

素数

定义

大于 $1$ 的整数 $p$，若它的正因子只有 $1$ 和 $p$ 本身，称为 素数（Prime Number，质数）；大于 $1$ 且不是素数的整数称为 合数（Composite Number）。

$1$ 既不是素数也不是合数——这不是抠字眼，而是为了让「唯一分解」成立（否则可以随便塞进任意多个 $1$）。最小的素数是 $2$，也是 唯一的偶素数，往后所有素数都是奇数。

素数是整数的「乘法原子」：它们不能再被拆小，而一切大于 $1$ 的整数都由它们相乘搭建而成。

素数判定

试除法：判断 $n$（$n>1$）是否为素数，只需检验 $2$ 到 $\lfloor\sqrt n\rfloor$ 之间有没有因子。

为什么到 $\sqrt n$ 就够了？因为若 $n=ab$ 且 $a\le b$，则 $a\le\sqrt n$——两个因子不可能都大于 $\sqrt n$，否则乘积超过 $n$。所以只要在 $\sqrt n$ 以内没找到因子，就再也不会有了。复杂度 $O(\sqrt n)$。

例：判 $n=221$ 是否为素数。$\lfloor\sqrt{221}\rfloor=14$，逐个试除 $2\sim 14$：$221$ 是奇数（非 $2$ 倍数），数字和 $2+2+1=5$ 不被 $3$ 整除，末位非 $0/5$ 排除 $5$，$221=7\times 31+4$ 排除 $7$，$221=11\times 20+1$ 排除 $11$，$221=13\times 17$——找到因子！故 $221=13\times 17$ 是合数。实战中只需试除 $\sqrt n$ 以内的 素数 $2,3,5,7,11,13$ 即可，更省。

例：判 $n=211$。同样 $\lfloor\sqrt{211}\rfloor=14$，依次验证 $2,3,5,7,11,13$ 都不整除 $211$（$211=7\times 30+1=11\times 19+2=13\times 16+3$），故 $211$ 是素数。

算术基本定理

任意大于 $1$ 的整数 $n$ 都可以 唯一地 分解为素数的乘积（不计因子的排列顺序）：

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

这就是 算术基本定理（Fundamental Theorem of Arithmetic），又称 唯一分解定理。它分两层含义：存在性（总能分解成素数）和 唯一性（分解方式本质上只有一种）。存在性靠反复拆合数即可；唯一性才是真正深刻的部分，关键依赖一条引理——若素数 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$（欧几里得引理，可由裴蜀定理证明）。

提示

唯一分解之所以是「基石」，是因为它把整数的乘法结构 彻底坐标化 了：每个整数等价于一串素数指数 $(a_1,a_2,\dots)$。一旦换到这个视角，整除、$\gcd$、$\operatorname{lcm}$ 全都变成对指数的逐位比较：

$$\gcd=\prod p_i^{\min(a_i,b_i)},\quad \operatorname{lcm}=\prod p_i^{\max(a_i,b_i)}$$

$a\mid b$ 就等价于「$a$ 的每个素数指数都不超过 $b$ 的对应指数」。许多看似棘手的整除问题，换到指数上立刻变得显然。

由唯一分解还能直接读出因子相关的量：设 $n=\prod p_i^{a_i}$，则 $n$ 的正因子个数 $d(n)=\prod(a_i+1)$，正因子之和为 $\prod\frac{p_i^{a_i+1}-1}{p_i-1}$。这些会在 积性函数 里展开。

例：用唯一分解求 $\gcd$ 与 $\operatorname{lcm}$。设 $a=360,\ b=84$，先分解：

$$360=2^3\cdot 3^2\cdot 5,\qquad 84=2^2\cdot 3\cdot 7$$

对每个素数取指数的较小值得 $\gcd$、较大值得 $\operatorname{lcm}$：

$$\begin{aligned} \gcd&=2^{\min(3,2)}\cdot 3^{\min(2,1)}\cdot 5^{\min(1,0)}\cdot 7^{\min(0,1)}=2^2\cdot 3=12 \\ \operatorname{lcm}&=2^{\max(3,2)}\cdot 3^{\max(2,1)}\cdot 5^{\max(1,0)}\cdot 7^{\max(0,1)}=2^3\cdot 3^2\cdot 5\cdot 7=2520 \end{aligned}$$

验证对偶关系 $\gcd\cdot\operatorname{lcm}=12\times 2520=30240=360\times 84=ab$，吻合。

例：求 $n=360=2^3\cdot 3^2\cdot 5$ 的因子个数。每个素数的指数可独立取 $0\sim a_i$，故

$$d(360)=(3+1)(2+1)(1+1)=4\times 3\times 2=24$$

即 $360$ 恰有 $24$ 个正因子。因子和则为

$$\sigma(360)=(1+2+4+8)(1+3+9)(1+5)=15\times 13\times 6=1170$$

每个括号是该素数那一列的等比和，乘起来正对应「逐位独立选指数」的全部组合。

素数的无穷性

素数有无穷多个。最经典的是 欧几里得反证法：

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

$$N=p_1p_2\cdots p_k+1$$

$N$ 大于 $1$，所以它至少有一个素因子 $q$。但 $N$ 除以任何 $p_i$ 都余 $1$（因为 $p_i\mid p_1\cdots p_k$ 而 $p_i\nmid 1$），所以 $q$ 不在我们的名单里。这与「名单已包含全部素数」矛盾。因此素数必有无穷多个。

提示

常见的误解是「$N$ 一定是素数」。其实不然——$N$ 可能是合数，比如 $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\times509$。证明用到的只是「$N$ 有一个不在名单里的素因子」，并不需要 $N$ 本身是素数。

埃拉托斯特尼筛法

要一次性求出 $1\sim N$ 中所有素数，逐个试除太慢。埃拉托斯特尼筛法（Sieve of Eratosthenes）反其道而行：不去验证谁是素数，而是把合数都「划掉」。

从 $2$ 开始，每遇到一个还没被划掉的数 $p$，它必是素数；然后把 $p$ 的所有倍数 $2p,3p,4p,\dots$ 全部标记为合数。处理完 $\sqrt N$ 以内的素数后，剩下没被划掉的就全是素数。划倍数时从 $p^2$ 开始即可（更小的倍数已被更小的素因子划过）。

例：筛出 $1\sim 30$ 内的素数。$\sqrt{30}<6$，只需用 $2,3,5$ 划倍数：

$$\begin{aligned} p=2:\quad&\text{划掉 }4,6,8,10,12,14,16,18,20,22,24,26,28,30 \\ p=3:\quad&\text{划掉 }9,15,21,27\ (6,12,\dots\text{ 已被 }2\text{ 划过}) \\ p=5:\quad&\text{划掉 }25\ (10,15,20\text{ 已被划过}) \end{aligned}$$

从 $p^2$ 起划即体现在：$p=3$ 从 $9$ 开始、$p=5$ 从 $25$ 开始。剩下没划掉的

$$2,3,5,7,11,13,17,19,23,29$$

就是 $30$ 以内的全部 $10$ 个素数。

复杂度为 $O(N\log\log N)$，近乎线性。若想做到严格 $O(N)$，可用 线性筛（欧拉筛）——它保证每个合数只被它的 最小素因子 划掉一次，避免重复，还能顺带求出 积性函数。

例：体会线性筛「只被最小素因子划一次」的机制。维护一个已发现素数表 primes，对每个 $i$（从 $2$ 起），用每个 $p\in$ primes 去标记 $i\cdot p$ 为合数，一旦 $p\mid i$ 就立即停止内层循环。看 $i=12$ 这一步：当前 primes 含 $2,3,5,7,11$，先标记 $12\times 2=24$（$24$ 的最小素因子正是 $2$），由于 $2\mid 12$，立即 break——不会再去标记 $12\times 3=36$。$36$ 会留给 $i=18$ 时由 $p=2$ 标记（$36=18\times 2$，$36$ 的最小素因子也是 $2$）。正是这个 break 保证了 每个合数 $n=p\cdot(n/p)$ 仅在「$p$ 为 $n$ 最小素因子」时被划一次，总操作数恰为 $O(N)$。

素数分布

素数计数函数

$\pi(x)$ 表示不超过 $x$ 的素数个数。素数越往后越「稀」，但稀得有规律。素数定理（Prime Number Theorem，PNT）给出：

$$\pi(x)\sim\frac{x}{\ln x}\quad(x\to\infty)$$

直观讲：「在 $x$ 附近，大约每 $\ln x$ 个整数里就有一个素数」。$x$ 越大，$\ln x$ 越大，素数越稀疏，但永不枯竭。

著名猜想

素数分布里藏着一批最有名的未解难题：

• 孪生素数猜想：存在无穷多对相差 $2$ 的素数 $(p,p+2)$，如 $(3,5),(11,13)$（未证；张益唐证明了相差有界的素数对有无穷多组，是里程碑式进展）。
• 哥德巴赫猜想：每个大于 $2$ 的偶数都可写成两个素数之和（未证；陈景润证得「$1+2$」，即每个充分大的偶数是一个素数与一个至多两素数之积的和）。
• 黎曼猜想：刻画 $\pi(x)$ 误差项的精细程度，是数学界公认的头号未解之谜。