查看“︁整数整除”︁的源代码

'''整数整除'''（integer divisibility）表示一个整数是另一个整数的整数倍。例如 <math>12=3\cdot4</math>，所以说 3 整除 12，记作 <math>3\mid12</math>；而 12 除以 5 的商不是整数，记作 <math>5\nmid12</math>。左边的数称为右边的因数，右边称为左边的倍数。

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

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

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

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

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

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

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

[[File:Gezhi-teaching-foundation-euclid-tiles.svg|frame|center|alt=二百五十二乘一百九十八的矩形按欧几里得步骤分出边长一百九十八、五十四、三十六和十八的方块，右侧对应四行除法|每一次切下最大可容纳的正方形，都把问题留给较小的剩余矩形。]]

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

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

== 带余除法为何有唯一答案 ==
欧几里得算法使用了带余除法。对于任意整数 a 和正整数 b，总能唯一写成
<math display="block">a=bq+r,\qquad 0\le r<b,</math>
其中 q、r 都是整数。q 为商，r 为余数。

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

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

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

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

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

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

=== 互素为什么允许消去因子 ===
最大公因数为 1 的两个数叫'''互素'''。例如 8 与 9 互素，虽然它们都不是素数。裴蜀等式此时能写成 <math>ua+vb=1</math>。

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

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

== 整数方程怎样求出全部解 ==
现在问：用 252 和 198 的整数倍相加，能否得到 36？这就是方程
<math display="block">252x+198y=36,\qquad x,y\in\mathbb Z.</math>
最大公因数 18 整除右端 36，因此把裴蜀等式乘以 2，就得到一个解：
<math display="block">36=8\cdot252-10\cdot198,\qquad (x_0,y_0)=(8,-10).</math>

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

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

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

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

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

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

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

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

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

== 参考资料 ==
* [https://twjudson.github.io/aata-files/aata-html/integers-section-division-algorithm.html Thomas W. Judson，Abstract Algebra: Theory and Applications，The Division Algorithm]：带余除法、最大公因数和整除性质。
* [https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII2.html Euclid，Elements，VII.2，David Joyce 编注]。
* 相关条目：[[素数]]、[[同余]]、[[逻辑]]。
[[分类:数论]]