最大公约数

把一块 a × b 的长方形地板恰好铺成正方形瓷砖，瓷砖最大边长就是 gcd(a, b)。两数公共的“可整除粒度”里最大的那一档。

1. 质因数分解：a = p₁^α₁ · p₂^α₂ · …，b = p₁^β₁ · p₂^β₂ · …，gcd(a, b) = p₁^min(α₁,β₁) · p₂^min(α₂,β₂) · …。
2. 短除法：用一个共同的质因数依次除两数，直到商互质，左侧所有除数之积即 gcd。
3. 辗转相除（更相减损/欧几里得）：gcd(a, b) = gcd(b, a mod b)，一直递归到余 0。
4. 重要恒等式：gcd(a, b) × lcm(a, b) = a × b。

• “最大公因数”和“最小公倍数”常被混淆——一个取小指数，一个取大指数。
• 三数 gcd 可两两递推：gcd(a, b, c) = gcd(gcd(a, b), c)。