入门：辗转相除、贝祖定理与扩欧直觉

基于通用数论概念 · 核于 2026-07

速查

• GCD 定义：gcd(a, b) 是 a、b 公约数中最大的那个；规定 gcd(a, 0) = |a|、gcd(0, 0) = 0、gcd(a, b) = gcd(|a|, |b|)（结果非负）。
• 辗转相除核心递推：gcd(a, b) = gcd(b, a mod b)，递归到 b == 0 时返回 a——这一行是整个算法的灵魂。
• LCM 公式：lcm(a, b) = a × b / gcd(a, b)；为防溢出写 a / gcd(a, b) × b（先除后乘）。
• 复杂度：辗转相除法 O(log min(a, b))——每两步被除数至少缩到一半以下（拉梅定理 Lamé's theorem）。
• 贝祖定理：对任意整数 a、b，存在整数 x、y 使得 ax + by = gcd(a, b)——这就是「方程一定有整数解」的理论保证。
• 扩展欧几里得：在递归求 gcd 的同时回代求出贝祖等式的一组特解 (x, y)，常数因子与求 gcd 相同。
• 乘法逆元：a 在模 m 下的逆元 a⁻¹ 满足 a × a⁻¹ ≡ 1 (mod m)，当且仅当 gcd(a, m) == 1 时存在；可用扩欧求。
• gcd ≥ 1：只要 a、b 不全为 0，gcd(a, b) ≥ 1；gcd(a, b) == 1 称 a、b 互质（coprime）。
• gcd 的线性性：gcd(k×a, k×b) = k × gcd(a, b)——这是分数化简与批量缩放的理论基础。
• gcd 与 lcm 的积：gcd(a, b) × lcm(a, b) = |a × b|——两个量互为「对偶」。
• 多元素 gcd/lcm：gcd(a, b, c) = gcd(gcd(a, b), c)，可逐个归约；lcm 同理。
• 应用骨架：分数化简（除 gcd）→ 互质判断（gcd==1）→ 求逆元（扩欧）→ 解不定方程（gcd|c 判定）→ CRT。
• 进阶顺序：辗转相除与扩欧 → 分数化简与方程应用 → 参考。

一、GCD 是什么：最大公约数

给定两个整数 a、b（不全为 0），它们的公约数是同时整除两者的整数，其中最大的那个就是最大公约数 gcd(a, b)。几个边界与符号约定：

• gcd(a, 0) = |a|（任何数整除 0，所以公约数就是 a 的约数，最大是 |a|）。
• gcd(0, 0) = 0（约定，实际题目里几乎不出现）。
• gcd(a, b) = gcd(|a|, |b|)，结果总是非负——处理负数时取绝对值即可。
• 只要不全为 0，gcd(a, b) ≥ 1。

例子：gcd(12, 18) = 6（公约数 1,2,3,6，最大 6）；gcd(7, 13) = 1（互质）；gcd(100, 0) = 100。

关键性质

• 线性性：gcd(k×a, k×b) = k × gcd(a, b)。比如 gcd(12, 18) = 6，那么 gcd(24, 36) = 2 × 6 = 12。
• 结合性：gcd(a, b, c) = gcd(gcd(a, b), c)，可以逐个归约到多个数。
• 吸收律：gcd(a, gcd(a, b)) = gcd(a, b)——a 自己已经被 gcd(a, b) 「吸收」了。

这些性质是辗转相除能成立的代数基础。

二、辗转相除法：gcd(a, b) = gcd(b, a mod b)

辗转相除法（欧几里得算法）用一个优雅的递推把求 gcd 化为更小规模的问题：

gcd(a, b) = gcd(b, a mod b)

直到 b == 0，此时 gcd(a, 0) = a 就是答案。

为什么对

设 a = q × b + r（其中 r = a mod b，q 是商）。任何 a、b 的公约数 d 都满足 d | a 且 d | b，那么 d | (a - q×b) 即 d | r——所以 d 也是 b、r 的公约数。反过来 b、r 的公约数也是 a、b 的公约数。于是两组公约数完全相同，最大者自然相等：gcd(a, b) = gcd(b, r)。

手算示例：gcd(18, 12)

gcd(18, 12)
18 = 1 × 12 + 6   → gcd(12, 6)
12 = 2 × 6  + 0   → gcd(6, 0) = 6

所以 gcd(18, 12) = 6。每一步被除数严格递减（r < b），必然在有限步内归约到 b == 0。

代码（递归 + 迭代）

// 递归版（最直观）
function gcd(a, b) {
  a = Math.abs(a); b = Math.abs(b);
  return b === 0 ? a : gcd(b, a % b);
}
// 迭代版（避免栈、常数更小）
function gcdIter(a, b) {
  a = Math.abs(a); b = Math.abs(b);
  while (b !== 0) { [a, b] = [b, a % b]; }
  return a;
}

三、LCM：最小公倍数 = a × b / gcd

最小公倍数 lcm(a, b) 是 a、b 公倍数中最小的正数。它与 gcd 是一对「对偶」量，关系是：

lcm(a, b) = a × b / gcd(a, b)

所以求了 gcd，lcm 只是顺手一行的事。

溢出陷阱：先除后乘

直接 a × b / gcd 在中间 a × b 这步可能溢出（比如两个 10⁹ 的数乘起来超过 32 位整数范围）。正确写法是先除后乘：

function lcm(a, b) {
  const g = gcd(a, b);
  return Math.abs(a / g) * Math.abs(b); // a/g 必整除，再乘 b
}

a / gcd(a, b) 必然整除（因为 gcd 是 a 的约数），先做除法缩小数值再做乘法，避免溢出。

例子：lcm(4, 6) = 4 × 6 / gcd(4,6) = 24 / 2 = 12；lcm(7, 13) = 91（互质时 lcm 就是乘积）。

四、复杂度：为什么是 O(log min(a, b))

辗转相除的步数上界由**拉梅定理（Lamé's theorem）**给出：步数 ≤ 5 × (min(a, b) 的十进制位数)。直觉上：

• 每一步 a, b → b, a mod b，新的第二个数 a mod b < b，严格递减。
• 更强的不等式：每两步，较大的数至少缩到原来的一半以下。因为 a mod b < b ≤ a，且若 b > a/2 则 a mod b = a - b < a/2；若 b ≤ a/2 则 a mod b < b ≤ a/2。所以每两步至少折半。

因此总步数是 O(log min(a, b))。对 64 位整数，最多约 90 步——这就是它对大整数也极快的原因。最坏情况是相邻的斐波那契数（如 gcd(F_{n+1}, F_n) 要 n 步），这是构造出来的极端，日常数据远没这么多步。

五、贝祖定理：ax + by = gcd(a, b) 一定有解

贝祖定理（Bézout's identity）：对任意整数 a、b（不全为 0），存在整数 x、y 使得

a × x + b × y = gcd(a, b)

这是数论里最深刻的「存在性」结论之一。它说的是：gcd 是 a 和 b 的所有「整数线性组合」里最小的正值。

验证：gcd(18, 12) = 6

可以验证 18 × 1 + 12 × (-1) = 6——确实 x=1, y=-1 是一组解。这组解怎么系统性地求出来？这就是扩展欧几里得算法的事。

解不唯一：通解

若 (x₀, y₀) 是 ax + by = gcd(a, b) 的一组特解，那么通解是：

x = x₀ + k × (b / g)
y = y₀ - k × (a / g)        其中 g = gcd(a, b)，k 为任意整数

代入验证：a × (x₀ + k×b/g) + b × (y₀ - k×a/g) = ax₀ + by₀ + k(ab/g - ab/g) = gcd(a,b)，确实成立。

六、扩欧直觉：回代求 (x, y)

扩展欧几里得算法在递归求 gcd 的同时，把贝祖等式的解 (x, y) 「回代」算出来。核心观察：

设 gcd(a, b) 这一层，递归调用 gcd(b, a mod b) 已经返回了 b × x' + (a mod b) × y' = g 的解 (x', y')。注意 a mod b = a - (a div b) × b（q = a div b），代入：

g = b × x' + (a - q×b) × y'
  = a × y' + b × (x' - q × y')

所以本层的解就是 x = y'、y = x' - q × y'——从子问题的解 (x', y') 用 O(1) 推出本层解 (x, y)。递归到 b == 0 时 gcd(a, 0) = a，对应 a × 1 + 0 × 0 = a，即 x=1, y=0。这就是回代的完整链路，详见辗转相除与扩展欧几里得。

下一步

理解了 GCD/LCM 定义、辗转相除的 O(log) 复杂度来源与贝祖定理后，下一步是把扩欧的回代代码写熟、并掌握乘法逆元的求法，见辗转相除与扩展欧几里得。