整数整除

整数整除（integer divisibility）表示一个整数是另一个整数的整数倍。例如 $12=3\cdot 4$，所以说 3 整除 12，记作 $3\mid 12$；而 12 除以 5 的商不是整数，记作 $5\nmid 12$。左边的数称为右边的因数，右边称为左边的倍数。

一个铺砖问题能把整除的几个主要概念连起来：用大小相同的正方形砖，整齐铺满长 252 厘米、宽 198 厘米的矩形。假定砖边与矩形边平行，砖的边长取整数厘米，砖不切割，那么边长要同时整除 252 和 198。要使砖尽可能大，就要找这两个数的最大公因数。

因数与公因数

对整数 a、b，若存在整数 k 使 $b=ak$，就定义 $a\mid b$。k 必须是整数，这正是整除与普通除法的区别。

例如 12 的正因数为 $1,2,3,4,6,12$，18 的正因数为 $1,2,3,6,9,18$，共同的正因数是 1、2、3、6，最大的为 6。记为 $$gcd(12,18)=6.$$ 符号 gcd 是 greatest common divisor 的缩写。对不全为零的整数 a、b，$gcd(a,b)$ 定义为最大的正公因数。

负号不影响正因数。例如 $-3\mid 12$，因为 $12=(-3)(-4)$；$3\mid -12$ 也成立。任意整数都整除 0，因为 $0=a\cdot 0$。于是非零 a 满足 $gcd(a,0)=|a|$。若两个数都为零，则每个正整数都是公因数，没有最大的一个；本条不另行定义 $gcd(0,0)$。

上述整除定义还给出 $0\mid 0$，因为存在整数 k 使 $0=0k$；零不整除非零整数。这是在判断一个乘法等式能否成立，并没有赋予除以零的运算一个值。

为什么可以把大数换成余数

列出 252 和 198 的全部因数可以解铺砖问题，但还有一种更短的办法。先把 252 除以 198： $$252=198+54.$$ 若砖的边长 d 同时整除 252 和 198，就也整除两者的差 54。反过来，若 d 同时整除 198 和 54，它便整除二者之和 252。因此，“252 与 198 的共同因数”恰好等于“198 与 54 的共同因数”。

接着计算： $$\begin{array}{cc}252& =1\cdot 198+54,\\ 198& =3\cdot 54+36,\\ 54& =1\cdot 36+18,\\ 36& =2\cdot 18+0.\end{array}$$ 也可以在原矩形内看到这些除法。下图先切出左侧边长 198 的正方形，余下宽 54 的长条；从长条中取出三个边长 54 的正方形，底部剩下 54×36 的小矩形；继续切分，最后得到边长 18 的小方块。这些不同大小的方块表示求余过程，并非原题要求的同尺寸铺法；得到 18 后，其他各边长都能再按 18 等分。

每一次切下最大可容纳的正方形，都把问题留给较小的剩余矩形。

每行都用“除数与余数”代替上一对数。第三行把问题归为求 36、18 的最大公因数；最后一行说明 18 已经整除 36，所以 $$gcd(252,198)=18.$$ 正方形砖的最大边长为 18 厘米。沿两边分别铺 $252/18=14$ 块和 $198/18=11$ 块，总数为 $14\cdot 11=154$ 块。每一步保存了全部公因数，所以所得的不仅是一个可用边长，而且是最大的边长。

这个过程叫欧几里得算法，也称辗转相除法。一般地，若 $$a=bq+r,$$ 那么共同整除 a、b 的数必整除 $r=a-bq$；共同整除 b、r 的数也必整除 $a=bq+r$。于是 $$gcd(a,b)=gcd(b,r).$$ 正余数一次比一次小，最终必出现余数零。最后一个非零余数就是最大公因数。

带余除法为何有唯一答案

欧几里得算法使用了带余除法。对于任意整数 a 和正整数 b，总能唯一写成 $$a=bq+r,0\le r<b,$$ 其中 q、r 都是整数。q 为商，r 为余数。

例如 $17=5\cdot 3+2$；对负数则有 $-17=5(-4)+3$。虽然也能写出 $-17=5(-3)-2$，但后一式余数为负，不是所规定的形式。

为什么总能选到合适的余数？考虑所有形如 $a-bq$ 的非负整数。把 q 取得足够负，总能得到这样的数。非负整数中的非空集合有最小元素，设这里的最小元素为 r。如果 $r\ge b$，那么 $r-b$ 仍非负，而且仍是同样的形式，却比 r 小，矛盾。因此 $0\le r<b$。

再看唯一性。若有 $$a=bq+r=b{q}^{\prime }+r^{\prime },0\le r,r^{\prime }<b,$$ 相减得到 $b(q-q^{\prime })=r^{\prime }-r$。右侧绝对值小于 b；左侧若非零，其绝对值至少为 b。两边只能都为零，所以 $q=q^{\prime }$、$r=r^{\prime }$。余数的规定范围正是唯一性的来源。

把最大公因数写回原来的两个数

铺砖问题中找到的 18，还能由 252 和 198 加减得到。沿着求余过程倒着代入： $$\begin{array}{cc}18& =54-36\\ & =54-(198-3\cdot 54)\\ & =4\cdot 54-198\\ & =4(252-198)-198\\ & =4\cdot 252-5\cdot 198.\end{array}$$ 每个余数都由前面的两个数相减得到，因此不断回代，最终总会成为原来两数的整数倍之和。这给出裴蜀等式：若 a、b 不全为零，则存在整数 u、v，使 $$gcd(a,b)=ua+vb.$$ u、v 可以为负，也通常不是唯一的。“整数线性组合”就是指这样的整数倍相加。

反过来，任何共同因数 d 都整除这些组合。若 $a=ds$、$b=dt$，则 $$ua+vb=d(us+vt).$$ 例如只看等式 $18=4\cdot 252-5\cdot 198$，就知道每个共同因数都整除 18；再验证 18 本身整除 252、198，便能独立确认它是最大公因数。

这还给出另一个描述：最大公因数是所有正的整数线性组合中最小的一个。一方面它本身能表示成组合；另一方面任意组合都是它的倍数，正的倍数不会比它小。

互素为什么允许消去因子

最大公因数为 1 的两个数叫互素。例如 8 与 9 互素，虽然它们都不是素数。裴蜀等式此时能写成 $ua+vb=1$。

若 a、b 互素，并且 $a\mid bc$，把上式乘以 c，得到 $$c=uac+vbc.$$ 右边第一项显然被 a 整除，第二项由已知条件也被 a 整除，所以 $a\mid c$。这就是互素情况下的乘积消去性质。

没有互素条件就可能失败。6 整除 $2\cdot 3$，却既不整除 2 也不整除 3；4 和 6 都整除 12，它们的积 24 却不整除 12。共同的因子使直接相乘或消去失去了原来的含义。素数与同余会继续使用互素消去性质。

整数方程怎样求出全部解

现在问：用 252 和 198 的整数倍相加，能否得到 36？这就是方程 $$252x+198y=36,x,y\in \mathbb{Z}.$$ 最大公因数 18 整除右端 36，因此把裴蜀等式乘以 2，就得到一个解： $$36=8\cdot 252-10\cdot 198,(x_0,y_0)=(8,-10).$$

要找其余解，把任意解减去这个特解： $$252(x-8)+198(y+10)=0.$$ 除以 18，整理为 $14(x-8)=-11(y+10)$。由于 11 与 14 互素，11 整除 $x-8$，故可以写成 $x-8=11t$，其中 t 为整数。代回后 $y+10=-14t$，所以全部整数解为 $$x=8+11t,y=-10-14t,t\in \mathbb{Z}.$$ 任意整数 t 代回时，参数项 $252\cdot 11t$ 和 $-198\cdot 14t$ 抵消，常数项为 $2016-1980=36$。这既验证每个列出的解都成立，也说明任意解都已包含在参数式中。

若 x、y 表示物品数量，还须非负。第一式要求整数 $t\ge 0$，第二式要求 $t\le -1$，无法同时满足。因此有整数解，却没有非负整数解。如果右端换成 35，18 不整除它，连整数解也不存在。

一般地，对不全为零的 a、b，方程 $ax+by=c$ 有整数解的充要条件是 $gcd(a,b)\mid c$。必要性来自共同因数整除每个组合；充分性来自把裴蜀等式乘以 $c/gcd(a,b)$。若 a、b 都非零，记 $d=gcd(a,b)$，从任一特解出发可得到 $$x=x_0+\frac{b}{d}t,y=y_0-\frac{a}{d}t,t\in \mathbb{Z}.$$ 某个系数为零时，直接求剩下的单个整除方程即可。

公因数与公倍数解决不同的问题

原铺砖问题中，边长要同时“放进”252 和 198，因此求最大公因数。若两个事件每 12 分钟、每 18 分钟发生一次，并且现在同时发生，下一次同时发生的等待时间须是两个周期的公共倍数。

12 的正倍数依次为 12、24、36、48……；18 的正倍数依次为 18、36、54……。最早重合在 36，称为最小公倍数，记作 $\mathrm{lcm}(12,18)=36$。

一般对正整数 a、b，令 $d=gcd(a,b)$，写成 $a=d{a}^{\prime }$、$b=d{b}^{\prime }$，其中 a′、b′ 互素。$d{a}^{\prime }{b}^{\prime }$ 是共同倍数。若 M 是任意共同倍数，写 $M=d{a}^{\prime }k$；由 $d{b}^{\prime }\mid M$ 可知 $b^{\prime }\mid a^{\prime }k$。互素消去给出 $b^{\prime }\mid k$，故 $d{a}^{\prime }{b}^{\prime }\mid M$。这证明它是最小的正共同倍数，于是 $$\mathrm{lcm}(a,b)=\frac{ab}{gcd(a,b)}.$$ 对 12、18，得到 $12\cdot 18/6=36$。若两个事件最初不同时发生，还要考虑开始时间之差，问题便转为同余方程。

最大公因数也能把分数一次约到最简： $$\frac{252}{198}=\frac{14}{11}.$$ 若约分后的 14、11 还有大于 1 的公因数，把它乘以 18 就会得到原两数更大的公因数，与最大性矛盾。因此使用最大公因数约分后，分子、分母必互素。

历史

欧几里得《几何原本》第七卷命题二记载了求两个数最大公度量的过程，使用反复相减的表述。一次带余除法相当于把连续减去若干次合并起来，形成今天常见的欧几里得算法。原文及逐步解释见 David Joyce 编注的《几何原本》VII.2。

古代文本处理的是正的数量；现代整数语言则把过程扩展到负数与零，并用线性组合解释回代。于是同一个算法既能回答长度怎样分割，也能用于求整数方程和模逆元。

参考资料

• Thomas W. Judson，Abstract Algebra: Theory and Applications，The Division Algorithm：带余除法、最大公因数和整除性质。
• Euclid，Elements，VII.2，David Joyce 编注。
• 相关条目：素数、同余、逻辑。