最大公约数
zuì dà gōng yuē shù
最大公约数（GCF）是能同时整除两个或更多个数的最大的数。
Formula
\text{GCF}(a,b) = \text{product of shared prime factors with minimum exponents}
Definition
两个或更多个数的最大公约数（GCF，也称最大公因数或 GCD）是能同时整除它们的最大的数。可以通过列出因数、进行质因数分解（对每个共有质数取最小指数）或使用欧几里得算法 $\text{GCF}(a,b) = \text{GCF}(b, a \bmod b)$ 来求得。从代数角度看，$\text{GCD}(a,b)$ 是 $\mathbb{Z}$ 中理想 $a\mathbb{Z} + b\mathbb{Z}$ 的生成元，等于 $\min\{ax + by : x,y \in \mathbb{Z}, ax+by > 0\}$；贝祖等式保证存在整数 $x,y$ 使得 $ax + by = \text{GCD}(a,b)$，最大公约数的概念可以推广到任意欧几里得整环或主理想整环。
Example
$12$ 和 $18$ 的最大公约数：$12$ 的因数是 $1,2,3,4,6,12$，$18$ 的因数是 $1,2,3,6,9,18$，它们共有的最大因数是 $6$，可用来把 $12/18$ 化简为 $2/3$。$\text{GCF}(48, 36)$：$48 = 2^4 \times 3$，$36 = 2^2 \times 3^2$，所以 $\text{GCF} = 2^2 \times 3 = 12$，这与欧几里得算法的链条 $\text{GCF}(48,36) = \text{GCF}(36,12) = \text{GCF}(12,0) = 12$ 一致。$\text{GCD}(48,36) = 12$ 的贝祖系数为 $12 = 48(1) + 36(-1)$，可由扩展欧几里得算法求得，这在密码学中计算模逆元时至关重要。
Key Insight
最大公约数在化简分数时非常有用。欧几里得算法是已知最古老的算法之一（欧几里得，约公元前300年），也是最高效的算法之一，其运行步数为 $O(\log(\min(a,b)))$。在任意主理想整环中，最大公约数都可以通过理想 $aR + bR$ 来定义；对于高斯整数 $\mathbb{Z}[i]$，$\text{GCD}(1+i, 3) = 1+i$，因为 $|1+i|^2 = 2$ 以相容的方式整除 $3$ 的分解式。