欧几里得算法（最大公约数）

数学与数论 · 辗转相除 · O(log min(a, b))

两千年前的取模递推

求两个数的最大公约数 gcd(a, b)（能同时整除它俩的最大整数），最古老也最快的办法是欧几里得算法（辗转相除）。它基于一个简单的事实：gcd(a, b) = gcd(b, a mod b)——a 和 b 的公约数，跟 b 和「a 除以 b 的余数」的公约数完全一样。于是不断用 (b, a mod b) 替换 (a, b)，数越缩越小，直到余数变 0，此时的被除数就是答案。因为每两步余数至少减半，只需 O(log min(a, b)) 步。

为什么？把它铺成正方形

有一个特别漂亮的几何解释：gcd(a, b) 等于能把一个 a×b 的矩形无缝铺满的最大正方形的边长。想铺满矩形，先尽量塞进边长等于短边的大正方形（能塞 ⌊a/b⌋ 个），塞完剩下一个更扁的小矩形 (a mod b) × b；再对这个小矩形做同样的事……每一步「切正方形」正好对应算术里的「取模」。切到某个正方形正好把矩形铺满、没有零头，那个最小正方形的边长就是 gcd。如果最小正方形是 1×1，就说明两数互质。

下面固定 gcd(30, 18)。点「下一步」逐步看：琥珀描边是这一步刚切下的正方形（格子里标着边长）、虚线框是还没铺的剩余小矩形。走过三步——30÷18=1 余 12、18÷12=1 余 6、12÷6=2 余 0——矩形被 18、12、6、6 四个正方形恰好铺满，最小的正方形边长 6 就是答案。右侧代码随每一步同步高亮。

求 gcd(30, 18)：把它看成一个 30×18 的矩形，反复从长边切下能放进去的最大正方形

1function gcd(a: number, b: number): number {
while (b !== 0) {          // 余数不为 0 就继续切
  const r = a % b;         // a 除以 b 的余数（= 切完正方形后剩下的边）
  a = b;                   // 除数变被除数
  b = r;                   // 余数变除数
}
return a;                  // b=0 时 a 就是最大公约数（最小正方形边长）
8}

矩形30×18

递推gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6

1 / 5

又快又是基石

递推：gcd(a, b) = gcd(b, a mod b)，余数为 0 时被除数即答案。
几何：能铺满 a×b 矩形的最大正方形边长 = gcd；最小正方形 = 1 ⟺ 互质。
复杂度：O(log min(a, b))，最坏情况是相邻斐波那契数。
延伸：扩展欧几里得在求 gcd 的同时解出 ax + by = gcd，是模逆元、解同余方程的基础。

欧几里得算法是数论与密码学的地基：约分、通分、求模逆元（RSA 解密的一步）、中国剩余定理都离不开它。它的扩展版还能一并算出让 ax + by = gcd(a, b) 成立的整数 x, y（Bézout 系数）——那是这条线自然的下一站。

算法可视化

欧几里得算法（最大公约数）

两千年前的取模递推

为什么？把它铺成正方形

又快又是基石