整除、最大公约数与裴蜀定理

整除是初等数论里最先出现、也最常被调用的关系。最大公约数、最小公倍数和裴蜀定理，其实都在回答同一件事：两个整数能共同生成哪些倍数。把这几条写清楚，后面的同余和逆元才有地方站。下面把定义、证明、手算和代码放在一起。

整除在说什么

整数 $a$ 整除整数 $b$，记作

意思是存在整数 $k$，使得 $b=ak$。这时称 $a$ 是 的因数， 是 的倍数。例如 ，因为 ；但 。

约定任何非零整数都整除 $0$，因为 $0=a\cdot 0$。反过来，$0$ 只整除 $0$：若 $0\mid b$，则 $b=0\cdot k=0$。符号 表示不整除。

整除不看正负：$a\mid b$ 当且仅当 $|a|\mid|b|$（$a\neq 0$）。因数通常取正的来讨论，但定义本身对负数同样成立，例如 $-6\mid 18$。写证明时把符号先收掉，往往更干净。

几条天天用到的性质：

1. 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。
2. 若 $a\mid b$ 且 $a\mid c$，则对任意整数 ，有 。

第一条：存在 $k,\ell$ 使 $b=ak$、$c=b\ell$，于是 $c=a(k\ell)$。

第二条：存在 $k,\ell$ 使 $b=ak$、$c=a\ell$，于是 $bx+cy=a(kx+\ell y)$。整除对线性组合封闭，后面几乎每条定理都要用它。

第三条：存在 $k,\ell$ 使 $b=ak$、$a=b\ell$，于是 $a=a(k\ell)$。若 $$，则 ，整数只能是 ，故 。 时由 只能有 。

带余除法是整除的定量版本。对任意整数 $a$ 和正整数 $b$，存在唯一的整数 $q,r$，使得

$r=0$ 恰好就是 $b\mid a$。存在性可以取 $q=\lfloor a/b\rfloor$，再令 $r=a-bq$，则 。唯一性用反证：若另有 ，则 。左边是 的倍数，右边绝对值小于 ，只能两边都是 。

带余除法把「能不能整除」变成「余数是不是零」，也给后面的辗转相除准备好了原料：每做一次，问题里的数就变小，但公约数集合不变。

最大公约数

正整数 $d$ 称为 $a,b$ 的公约数，若 $d\mid a$ 且 $d\mid b$。所有公约数里最大的那个，记作 $\gcd(a,b)$，也常写成 。约定 （）； 在数学上通常不定义，写程序时要单独拦住。

欧几里得算法把带余除法变成计算：

余数严格递减且非负，有限步后变成 $0$，此时回到 $\gcd(a,0)=|a|$。步数不超过较小那个数的位数量级，所以手算大数也只是多写几行除法，不必分解质因数。

这一步为什么成立？设 $a=bq+r$。任何同时整除 $a$ 和 $b$ 的数，由线性组合封闭性，也整除 $r=a-bq$；反过来，整除 $b$ 和 的数也整除 。所以 与 的公约数集合完全相同，最大者当然相同。

这立刻给出一个比「最大」更强的结论：$\gcd(a,b)$ 是所有公约数的倍数。换句话说，公约数集合恰好是 $d=\gcd(a,b)$ 的全体正因数。跟着欧几里得走即可：每一步公约数集合不变，最后一步是 $\gcd(d,0)$，其公约数就是 $d$ 的正因数。

互素是 $\gcd=1$ 的专名。两个偶数绝不互素；相邻整数一定互素，因为任何公约数都整除它们的差 $1$。更一般地，$\gcd(a,b)=\gcd(a,b-a)$，差不会引入新的公约数。

还有两条计算时很省事的性质。第一，$\gcd(ka,kb)=|k|\gcd(a,b)$。把公因子提出去再算，数字立刻变小。第二，多个整数的最大公约数可以两两归约：

结合律成立，是因为两边描述的都是同时整除 $a,b,c$ 的最大正整数。分数约分、多项式系数提取，用的都是这一套。

最小公倍数

正整数 $m$ 称为 $a,b$ 的公倍数，若 $a\mid m$ 且 $b\mid m$。所有正公倍数里最小的那个，记作 $\mathrm{lcm}(a,b)$。

和 gcd 对偶的一条恒等式是：对非零整数 $a,b$，

一条路走素因数分解。设

则

而 $\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta$，两边乘起来就是 $|ab|$。

不想依赖唯一分解也可以。设 $d=\gcd(a,b)$，写 $a=da'$、$b=db'$，则 。断言 。它显然是公倍数。若 是任一正公倍数，则 、，于是 ，从而 。因为 与 互素， 必须整除 ，故 是 的倍数。最小正者就是 。

这里用到了一次「互素则能约掉」：若 $\gcd(a',b')=1$ 且 $a'\mid b'\ell$，则 。证明可以先承认裴蜀：存在 使 ，两边乘 得 ，左边两项都被 整除。不想提前用裴蜀，也可以从素因子上看： 的每个素因子都不在 里，只能进入 。

于是计算 lcm 不必另写一套辗转相除：先算 gcd，再

写代码时先除后乘，避免中间溢出。Python 整数没有上限，但这个习惯在其他语言里能救命。

裴蜀定理

设 $a,b$ 不全为零，$d=\gcd(a,b)$。裴蜀定理说：存在整数 $x,y$，使得

并且，$ax+by$ 能取到的全体整数，恰好是 $d$ 的倍数。

后半句几乎是整除性质的直接推论。左边是 $a,b$ 的线性组合，必被 $d$ 整除，所以只能落在 $d$ 的倍数上。前半句保证 $d$ 本身也能取到，于是所有倍数都能取到：把表示 $d$ 的那组系数乘上 $k$，就得到 $dk$。

存在性有两条常见证法。一条不依赖算法，只靠良序：考虑所有正的线性组合 $\{ax+by:x,y\in\mathbb{Z},\,ax+by>0\}$，取其中最小者 $d_0$。带余除法把 除以 ，余数 仍是线性组合，且 。若 就与最小性矛盾，故 ，即 。同理 ，所以 是公约数。任何公约数又整除一切线性组合，于是 就是最大公约数。这条路同时证明了「最小正线性组合等于 gcd」。

另一条跟着欧几里得回代，也更适合写成代码。算法最后一步得到余数 $d$，而每一步的余数都是前两个数的整数组合。形式化地，维护

初始 $r_0=a$（系数 $1,0$），$r_1=b$（系数 $$）。辗转相除给出 ，于是

最后一个非零余数就是 $d$，对应的系数就是要的 $x,y$。这就是扩展欧几里得算法。

一个立刻能用的推论：不定方程 $ax+by=c$ 有整数解，当且仅当 $d\mid c$。一次同余方程的可解性也落在同一条判别上，那是另一篇文章的事。

另一个推论：$\gcd(a,b)=1$ 当且仅当存在 $x,y$ 使 $ax+by=1$。互素因此有一个「能拼出 $1$」的刻画，不必先列出全部公约数再比较。

特解一旦到手，通解是齐次部分的平移。若 $ax_0+by_0=c$，则

代入即得 $a\cdot(b/d)-b\cdot(a/d)=0$，所以加上这一项不改变线性组合的值。这也说明特解有无穷多组，扩展欧几里得只负责交出其中一组。

三个以上整数同样有裴蜀形式：$\gcd(a_1,\dots,a_n)$ 能写成 $a_1x_1+\cdots+a_nx_n$。先对前两个做出组合，再和下一个做，归纳即可。

手算例子

例一：辗转相除并回代

求 $\gcd(252,198)$，并找出一组裴蜀系数。

所以 $d=18$。从倒数第二个等式开始回代：

验算：$4\cdot 252-5\cdot 198=1008-990=18$。于是 $252x+198y=18$ 有特解 。通解加上齐次部分：

这里 $11=198/18$，$14=252/18$。取 $t=0$ 就是刚才那组；取 $t=-1$ 得到 $(-7,9)$，同样有 。

例二：lcm，以及拼得出与拼不出

求 $\mathrm{lcm}(252,198)$。已有 $d=18$，所以

验算：$2772/252=11$，$2772/198=14$。因为 $11$ 与 $14$ 互素，不可能再缩小而不拆开其中一个因子，所以 $2772$ 确是最小正公倍数。

再看 $252x+198y=12$。$18\nmid 12$，裴蜀定理直接判无解。直观上，$252$ 和 $198$ 都是 $18$ 的倍数，线性组合跨不过 $18$ 这一关。

改成 $252x+198y=54$。$18\mid 54$，有解。把例一的系数乘 $3$：

通解是 $x=12+11t$，$y=-15-14t$。

例三：互素判定

$\gcd(35,18)$。

$\gcd=1$，二者互素。回代：$1=18-17=18-(35-18)=2\cdot 18-1\cdot 35$。所以

能拼出 $1$，就能拼出任意整数：两边乘 $c$，得到 $35x+18y=c$ 的一组解。这和「公约数只有 $\pm 1$」是同一件事的两种说法。

想要非负解时，通解就派上用场。例如 $35x+18y=1$ 的通解是 $x=-1+18t$、$y=2-35t$。取 得到 ，取 得到 ，两组里 都一正一负。要两个系数同时非负，右边必须足够大，这已经越出「有没有整数解」的范围，但步长仍然由 和 决定。

一份可直接用的实现

普通欧几里得只给 $d$。扩展欧几里得在辗转相除的同时，把裴蜀系数也记下来。迭代写法最适合写代码：维护两组系数，使每一步的余数都能写成 $a$、$b$ 的整数组合。

跑一下就能对上前面的手算。egcd 的时间是 $O(\log\min(|a|,|b|))$，最坏情形接近斐波那契数那一组输入。若还要通解，特解加上 $\bigl(b/d,\,-a/d\bigr)$ 的整数倍即可。

math.gcd 从 Python 3.5 起对负数返回非负值，lcm 里先除后乘，和上面的恒等式一致。gcd(0,0) 在 math 里是 $0$，和这里的约定对齐。负数输入不必先取绝对值再算，系数符号会跟着余数一起走，最后再按需要翻一次即可。

写代码和手算时容易踩的坑

先除后乘再取绝对值。$\mathrm{lcm}(a,b)=|ab|/\gcd$ 若先算 $ab$，在定长整数里可能溢出；先算 $a/\gcd$ 再乘 $b$，中间更小。

裴蜀系数不唯一，验算只看 $ax+by$ 等不等于 $d$。扩展欧几里得给出的只是其中一组，和手算回代可能差一个齐次项，两边都对。

$d$ 的符号要事先约定。欧几里得对负数会走出负余数或负的 $d$，定理陈述里通常取 $d>0$。比较、整除判断、再乘 $c/d$ 之前，先把 $d$ 收成正的。

通解的步长是 $b/d$ 和 $-a/d$，不是 $d$。例一里相邻特解的 $x$ 相差 $11$，不是 $18$。

$\gcd(a,0)=|a|$，但 $\gcd(0,0)$ 没有「最大」正公约数。调用方若可能传入双零，不要默默返回 $0$ 然后继续除。

整除判断用模，不要用浮点除法。b % a == 0 对整数成立；写成 b / a 再看是不是整数，会在大数上失真。

不要把「能整除」和「互素」搞反。$a\mid b$ 是单向的倍数关系；互素是公约数只有 $\pm 1$。$4\mid 12$ 但二者绝不互素。

约分时只约 $\gcd$，不要误把其中一个数除尽。把 $252/198$ 化成最简分数，应同时除以 $18$ 得到 $14/11$，而不是看见偶数就只除 $2$。

多个数求 lcm 时不要先两两相乘再除。正确做法是 $\mathrm{lcm}(a,b,c)=\mathrm{lcm}(\mathrm{lcm}(a,b),c)$，每一步都用 $|ab|/\gcd$。直接乘起来会把公共因子算重。

这三件事其实是一件事

整除给出线性组合封闭性，欧几里得证明公约数集合沿余数不变，裴蜀定理再把最大公约数本身写成组合。lcm 只是把同一套因数关系翻到倍数一侧。把这几条串起来，后面的同余、逆元和中国剩余定理都只是在模意义下重说一遍。

手算时先求 $d$，再问 $d$ 能不能整除目标；写代码时让扩展欧几里得同时交出 $d$ 和系数。存在性、特解、通解分开，验算就对得上。把这三步养成习惯，后面遇到模逆、分数化简和周期问题，都不必再从头发明一套语言。