整数整除：修订间差异

2026年9月20日 (日) 07:17的最新版本

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

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

因数与公因数

对整数 a、b，若存在整数 k 使 $b = a k$ ，就定义 $a ∣ 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 ∣ 12$ ，因为 $12 = (- 3) (- 4)$ ； $3 ∣ - 12$ 也成立。任意整数都整除 0，因为 $0 = a \cdot 0$ 。于是非零 a 满足 $gcd (a, 0) = | a |$ 。若两个数都为零，则每个正整数都是公因数，没有最大的一个；本条不另行定义 $gcd (0, 0)$ 。

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

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

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

接着计算： $\begin{matrix} 252 & = 1 \cdot 198 + 54, \\ 198 & = 3 \cdot 54 + 36, \\ 54 & = 1 \cdot 36 + 18, \\ 36 & = 2 \cdot 18 + 0. \end{matrix}$ 也可以在原矩形内看到这些除法。下图先切出左侧边长 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 = b q + r,$ 那么共同整除 a、b 的数必整除 $r = a - b q$ ；共同整除 b、r 的数也必整除 $a = b q + r$ 。于是 $gcd (a, b) = gcd (b, r) .$ 正余数一次比一次小，最终必出现余数零。最后一个非零余数就是最大公因数。

带余除法为何有唯一答案

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

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

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

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

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

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

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

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

互素为什么允许消去因子

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

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

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

整数方程怎样求出全部解

现在问：用 252 和 198 的整数倍相加，能否得到 36？这就是方程 $252 x + 198 y = 36, x, y \in ℤ .$ 最大公因数 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 = 11 t$ ，其中 t 为整数。代回后 $y + 10 = - 14 t$ ，所以全部整数解为 $x = 8 + 11 t, y = - 10 - 14 t, t \in ℤ .$ 任意整数 t 代回时，参数项 $252 \cdot 11 t$ 和 $- 198 \cdot 14 t$ 抵消，常数项为 $2016 - 1980 = 36$ 。这既验证每个列出的解都成立，也说明任意解都已包含在参数式中。

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

一般地，对不全为零的 a、b，方程 $a x + b y = c$ 有整数解的充要条件是 $gcd (a, b) ∣ 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 ℤ .$ 某个系数为零时，直接求剩下的单个整除方程即可。

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

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

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

一般对正整数 a、b，令 $d = gcd (a, b)$ ，写成 $a = d a^{'}$ 、 $b = d b^{'}$ ，其中 a′、b′ 互素。 $d a^{'} b^{'}$ 是共同倍数。若 M 是任意共同倍数，写 $M = d a^{'} k$ ；由 $d b^{'} ∣ M$ 可知 $b^{'} ∣ a^{'} k$ 。互素消去给出 $b^{'} ∣ k$ ，故 $d a^{'} b^{'} ∣ M$ 。这证明它是最小的正共同倍数，于是 $lcm (a, b) = \frac{a b}{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 编注。
相关条目：素数、同余、逻辑。

@@ 第1行： / 第1行： @@
-'''整数整除'''（integer divisibility）研究一个整数是否是另一个整数的整数倍。对整数 <math>a,b</math>，若存在整数 <math>k</math> 使 <math>b=ak</math>，就记 <math>a\mid b</math>，读作“<math>a</math> 整除 <math>b</math>”，并称 <math>a</math> 是 <math>b</math> 的因数。整除关系把因数、倍数、最大公因数和整数方程连接起来，是[[素数]]与[[同余]]理论的基础。本文始终在整数范围内讨论，除特别说明外，最大公因数取正值。
+'''整数整除'''（integer divisibility）表示一个整数是另一个整数的整数倍。例如 <math>12=3\cdot4</math>，所以说 3 整除 12，记作 <math>3\mid12</math>；而 12 除以 5 的商不是整数，记作 <math>5\nmid12</math>。左边的数称为右边的因数，右边称为左边的倍数。
-== “除得开”为什么必须指定整数范围 ==
+一个铺砖问题能把整除的几个主要概念连起来：用大小相同的正方形砖，整齐铺满长 252 厘米、宽 198 厘米的矩形。假定砖边与矩形边平行，砖的边长取整数厘米，砖不切割，那么边长要同时整除 252 和 198。要使砖尽可能大，就要找这两个数的最大公因数。
-十二能够按每组三个分成四组，对应 <math>12=3\cdot4</math>，所以 <math>3\mid12</math>。十二除以五也能得到一个有理数，但商不是整数，所以 <math>5\nmid12</math>。如果允许任意有理数商，任何非零整数都能“除”任何整数，整除关系就失去了区分作用。定义中的整数系数正是实质条件。
-负数不会改变因数的绝对大小：<math>-3\mid12</math>，因为商为负四；<math>3\mid-12</math> 也成立。每个整数都整除零，因为零是它的零倍。按本条采用的存在性定义，<math>0\mid0</math> 成立，而零不整除任何非零整数。这不表示可以进行除以零的运算；整除是一个乘法关系，不是已经求出的除法值。
+== 因数与公因数 ==
+对整数 a、b，若存在整数 k 使 <math>b=ak</math>，就定义 <math>a\mid b</math>。k 必须是整数，这正是整除与普通除法的区别。
-整除符号有方向。<math>a\mid b</math> 表示右侧是左侧的倍数，不能因为中文“被整除”的不同说法而反过来读取。对正整数，若 <math>a\mid b</math> 则 <math>a\le b</math>，但大小关系并不充分，例如五小于十二却不整除十二。整除描述的是乘法结构，而不是普通数轴顺序。
+例如 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>1,2,3,4,6,12</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>；零不整除非零整数。这是在判断一个乘法等式能否成立，并没有赋予除以零的运算一个值。
-若 <math>d\mid a</math> 且 <math>d\mid b</math>，那么对任意整数 <math>u,v</math> 都有 <math>d\mid ua+vb</math>。证明直接来自定义：写 <math>a=ds,b=dt</math>，便有 <math>ua+vb=d(us+vt)</math>，括号中的数仍是整数。这条性质是欧几里得算法与裴蜀等式的共同基础。
-整除还满足传递性：若 <math>a\mid b</math>、<math>b\mid c</math>，把两个整数倍表达式相接，就得到 <math>a\mid c</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>2\cdot3</math>，但既不整除二，也不整除三。只有当因数是素数，或附加适当互素条件时，才有更强的结论。“整除一个乘积就整除某个因子”不是一般整数的性质；这一边界解释了素数为何值得单独研究。
+接着计算：
+<math display="block">\begin{aligned}
+&=1\cdot198+54,\\
+&=3\cdot54+36,\\
+&=1\cdot36+18,\\
+&=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>a</math> 和正整数 <math>b</math>，存在唯一整数 <math>q,r</math> 满足
+<math display="block">\gcd(252,198)=18.</math>
-<math display="block">a=bq+r,\qquad 0\le r<b.</math>
+正方形砖的最大边长为 18 厘米。沿两边分别铺 <math>252/18=14</math> 块和 <math>198/18=11</math> 块，总数为 <math>14\cdot11=154</math> 块。每一步保存了全部公因数，所以所得的不仅是一个可用边长，而且是最大的边长。
-这称为带余除法定理。商可以是负数，但余数统一取非负且小于除数。这一区间条件使表示唯一；若不限制余数，把商增加一、余数减去除数，会得到无限多个同样正确的等式。
-例如 <math>-17=5(-4)+3</math>，所以按上述约定，商为负四、余数为三。写成 <math>-17=5(-3)-2</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>
+正余数一次比一次小，最终必出现余数零。最后一个非零余数就是最大公因数。
-存在性可用最小非负剩余量证明。在所有形如 <math>a-bq</math> 的非负整数中选最小者 <math>r</math>；这样的数总存在，因为把整数 <math>q</math> 取得足够负即可。如果 <math>r\ge b</math>，则 <math>r-b</math> 仍非负、仍有同样形式而且更小，矛盾，所以 <math>r<b</math>。这里使用了非负整数的良序性。
+== 带余除法为何有唯一答案 ==
+欧几里得算法使用了带余除法。对于任意整数 a 和正整数 b，总能唯一写成
+<math display="block">a=bq+r,\qquad 0\le r<b,</math>
+其中 q、r 都是整数。q 为商，r 为余数。
-唯一性也要证明。若 <math>a=bq+r=bq'+r'</math>，相减得到 <math>b(q-q')=r'-r</math>。右侧绝对值小于 <math>b</math>，而非零的 <math>b</math> 倍数绝对值至少为 <math>b</math>，因此两侧只能为零，商与余数分别相同。定理不仅告诉算法可以算出答案，也说明不同正确算法应当得到同一规范结果。
+例如 <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>a,b</math> 的最大公因数记为 <math>\gcd(a,b)</math>，定义为最大的正公因数。负号不影响结果，可先取绝对值。对非零 <math>a</math>，<math>\gcd(a,0)=|a|</math>；本文不为 <math>\gcd(0,0)</math> 规定值，以免把不同扩充约定混入入门定义。
-若 <math>a=bq+r</math>，则 <math>a,b</math> 与 <math>b,r</math> 拥有完全相同的公因数：共同整除前两者，就整除差 <math>r=a-bq</math>；共同整除后两者，也整除和 <math>a=bq+r</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>。余数的规定范围正是唯一性的来源。
-计算二百五十二与一百九十八：
+== 把最大公因数写回原来的两个数 ==
-<math display="block">\begin{aligned}252&=198+54,\\198&=3\cdot54+36,\\54&=36+18,\\36&=2\cdot18.\end{aligned}</math>
+铺砖问题中找到的 18，还能由 252 和 198 加减得到。沿着求余过程倒着代入：
-非零余数逐步变小，最后一个非零余数为十八，因此最大公因数是十八。验证原数分别为十八的十四倍与十一倍，可确认它确实是公因数；它是最大的理由来自每一步保持完整公因数集合，而不只是最后一次除法。
+<math display="block">\begin{aligned}
+&=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，便能独立确认它是最大公因数。
-== 回代得到裴蜀等式及其意义 ==
+这还给出另一个描述：最大公因数是所有正的整数线性组合中最小的一个。一方面它本身能表示成组合；另一方面任意组合都是它的倍数，正的倍数不会比它小。
-把上面的余数关系倒着代入，可得
-<math display="block">18=54-36=54-(198-3\cdot54)=4\cdot252-5\cdot198.</math>
-这不仅给出最大公因数，还把它表示成原来两数的整数线性组合。一般地，不全为零的整数 <math>a,b</math> 总存在整数 <math>u,v</math>，使
-<math display="block">\gcd(a,b)=ua+vb.</math>
-这称为裴蜀等式。扩展欧几里得算法就是在求余过程中同步追踪这些系数，或者计算结束后回代恢复它们。
-等式中的系数未必正，也通常不唯一。上例的负五完全正常，因为整数线性组合允许相减。若问题要求非负整数解，就附加了新的限制，裴蜀等式本身不保证满足。它说明整除约束下哪些整数可以由加减组合得到，而不是任何实际配比都能采用这种组合。
+=== 互素为什么允许消去因子 ===
+最大公因数为 1 的两个数叫'''互素'''。例如 8 与 9 互素，虽然它们都不是素数。裴蜀等式此时能写成 <math>ua+vb=1</math>。
-还可以反向刻画最大公因数：原两数的所有取正值的整数线性组合中，最小者就是最大公因数。取最小正组合 <math>d</math>，分别用它去除原两数；余数仍是整数线性组合，若为正就比 <math>d</math> 更小，矛盾，所以余数为零。于是 <math>d</math> 是公因数；任何公因数又整除每个线性组合，所以也整除 <math>d</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。共同的因子使直接相乘或消去失去了原来的含义。[[素数]]与[[同余]]会继续使用互素消去性质。
-== 整数方程的有解条件与全部解 ==
+== 整数方程怎样求出全部解 ==
-线性整数方程 <math>ax+by=c</math> 有整数解，当且仅当 <math>d=\gcd(a,b)</math> 整除 <math>c</math>。必要性来自共同因数整除每个线性组合；充分性来自裴蜀等式：把表示 <math>d</math> 的系数一起乘以 <math>c/d</math>，就得到目标右端。
+现在问：用 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>252x+198y=36</math> 有解，因为十八整除三十六。将上述裴蜀系数乘二，得到一个特解 <math>(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>
-代回时两个含参数项相消，常数部分为 <math>2016-1980=36</math>。要证明没有漏解，将任意解与特解相减，得到 <math>14(x-8)=-11(y+10)</math>；十四与十一互素，迫使 <math>x-8</math> 是十一的倍数，随后得到另一式。
+任意整数 t 代回时，参数项 <math>252\cdot11t</math> 和 <math>-198\cdot14t</math> 抵消，常数项为 <math>2016-1980=36</math>。这既验证每个列出的解都成立，也说明任意解都已包含在参数式中。
-若额外要求两个未知量非负，则第一式要求整数参数至少为零，第二式要求参数至多为负一，没有交集。因此方程有整数解，却没有非负整数解。这个完整例子说明“存在代数解”与“符合情境限制的解”并不相同。若把右端改为三十五，则连整数解也没有，因为十八不整除三十五。
-一般的全部解公式在 <math>a,b</math> 都非零时写为 <math>x=x_0+(b/d)t</math>、<math>y=y_0-(a/d)t</math>。如果某个系数为零，应直接按剩余单个整除条件处理，避免机械套用推导中隐含的非零假设。参数必须是整数，不能把实数方程解直线上的所有点都当成整数解。
-== 互素条件怎样恢复乘积消去 ==
-若 <math>\gcd(a,b)=1</math> 且 <math>a\mid bc</math>，则 <math>a\mid c</math>。由裴蜀等式取 <math>ua+vb=1</math>，乘以 <math>c</math> 得 <math>uac+vbc=c</math>；左边两项都被 <math>a</math> 整除，所以右边也是。这个证明精确指出互素条件的用途：它让一被写成适当的整数线性组合。
-素数整除乘积必整除某个因子的结论，可以从这里推出：若素数不整除第一个因子，它与该因子就互素，因而整除第二个。[[素数]]条目将用这一点证明唯一分解；[[同余]]条目则用它解释什么时候可以约去一个乘数。三个主题共享同一个整除机制，而不是三套互不相关的技巧。
-正整数 <math>a,b</math> 的最小公倍数记为 <math>\operatorname{lcm}(a,b)</math>，满足
-<math display="block">\gcd(a,b)\operatorname{lcm}(a,b)=ab.</math>
-把两数分别写成 <math>da',db'</math>，其中 <math>a',b'</math> 互素，则最小公倍数是 <math>da'b'</math>。任何共同倍数除以 <math>d</math> 后，同时含有互素的两个因子，因而必被它们的积整除，这证明了最小性。对十二与十八，最大公因数为六，最小公倍数为三十六，乘积关系为 <math>6\cdot36=12\cdot18</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>
+某个系数为零时，直接求剩下的单个整除方程即可。
-== 算法记载与现代语言 ==
+== 公因数与公倍数解决不同的问题 ==
-《几何原本》第七卷命题二记载了寻找两个数最大公度量的过程，采用反复相减的表达。现代带余除法把连续减去若干次合并成一步，构成今天常用的欧几里得算法。原文及解释可见 [https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII2.html David Joyce 编注的《几何原本》VII.2]。文献中的古代“数”与今天包括负数、零的整数范围并不完全相同。
+原铺砖问题中，边长要同时“放进”252 和 198，因此求最大公因数。若两个事件每 12 分钟、每 18 分钟发生一次，并且现在同时发生，下一次同时发生的等待时间须是两个周期的公共倍数。
-因此“欧几里得算法”是明确的历史归名，却不等于能够据此断言欧几里得首次发现了所有整除思想。本条使用的负数约定、函数式记号和整数线性组合语言，是现代组织方式。历史说明应区分可见的文献记载、后来的命名与现代一般化，不把它们压缩成一个未经证实的发明日期。
+的正倍数依次为 12、24、36、48……；18 的正倍数依次为 18、36、54……。最早重合在 36，称为'''最小公倍数'''，记作 <math>\operatorname{lcm}(12,18)=36</math>。
-== English overview ==
+一般对正整数 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>。这证明它是最小的正共同倍数，于是
-<div lang="en" class="math-english-summary">
+<math display="block">\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.</math>
-An integer a divides an integer b when b is an integer multiple of a. Divisibility is a relation defined through multiplication, so statements involving zero must not be confused with division by zero. Common divisors are preserved under integer linear combinations.
+对 12、18，得到 <math>12\cdot18/6=36</math>。若两个事件最初不同时发生，还要考虑开始时间之差，问题便转为[[同余]]方程。
-The division theorem gives a unique quotient and a remainder between zero and a positive divisor. The Euclidean algorithm repeatedly replaces a pair by the divisor and remainder. This preserves all common divisors, while decreasing positive remainders guarantee termination. Back substitution expresses the greatest common divisor as an integer linear combination, known as Bézout's identity.
+最大公因数也能把分数一次约到最简：
+<math display="block">\frac{252}{198}=\frac{14}{11}.</math>
+若约分后的 14、11 还有大于 1 的公因数，把它乘以 18 就会得到原两数更大的公因数，与最大性矛盾。因此使用最大公因数约分后，分子、分母必互素。
-A linear equation ax + by = c has integer solutions exactly when gcd(a,b) divides c. A worked example derives every integer solution and then shows why none satisfies an added nonnegativity requirement. Coprimality also explains valid cancellation in products and supports the theory of primes and congruences. The least common multiple records shared multiples without counting common factors twice. Historical discussion distinguishes Euclid's recorded subtraction procedure from its modern remainder formulation and from later integer notation.
+== 历史 ==
-</div>
+欧几里得《几何原本》第七卷命题二记载了求两个数最大公度量的过程，使用反复相减的表述。一次带余除法相当于把连续减去若干次合并起来，形成今天常见的欧几里得算法。原文及逐步解释见 [https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII2.html David Joyce 编注的《几何原本》VII.2]。
-== 编者评注（AI 辅助） ==
+古代文本处理的是正的数量；现代整数语言则把过程扩展到负数与零，并用线性组合解释回代。于是同一个算法既能回答长度怎样分割，也能用于求整数方程和模逆元。
-本条把欧几里得算法的“保持公因数不变”与“余数下降所以停止”分开证明，再用同一个算例完成回代和整数方程求解，避免算法步骤只是口令。零、负数与非负解限制均单独说明，因为它们最容易被默认约定遮蔽。内容由 AI 辅助整理；编者的取舍是先解释整数系数为什么重要，再连接素数和同余，不能据计算方便而扩大未说明的数域。
-== 参考资料与后续阅读 ==
+== 参考资料 ==
-* [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://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 编注]：最大公度量算法原文与解释。
+* [https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII2.html Euclid，Elements，VII.2，David Joyce 编注]。
-* 后续可读[[素数]]、[[同余]]、[[群]]；与[[逻辑]]中的存在性证明和反证法相联系。
+* 相关条目：[[素数]]、[[同余]]、[[逻辑]]。
 [[分类:数论]]