形式陈述

整数 $a,b$$a,b$（不全为零）的最大公约数是唯一正整数 $d$$d$，满足

$$ d\mid a, \quad d\mid b, \quad \text{且任意 }c\mid a,b\text{ 都有 }c\mid d. $$$$d\mid a,d\mid b,\text{且任意 }c\mid a,b\text{ 都有 }c\mid d.$$

记作 $d=\gcd(a,b)$$d=gcd(a,b)$。存在整数 $x,y$$x,y$ 使

$$ \gcd(a,b)=ax+by, $$$$gcd(a,b)=ax+by,$$

称为 Bézout 恒等式；它来自理想 $(a,b)=\gcd(a,b)\mathbb Z$$(a,b)=gcd(a,b)\mathbb{Z}$。通常约定 $\gcd(a,0)=|a|$$gcd(a,0)=|a|$。若 $\gcd(a,b)=1$$gcd(a,b)=1$，称 $a,b$$a,b$ 互素。更一般整环中的 gcd 若存在，只唯一到单位倍数；UFD 中每对非零元都有 gcd，但一般整环未必如此。

直觉

最大公约数不是按数值“最大的公共因子”这一偶然事实，而是整除偏序中支配全部公共因子的对象；正号约定消除了单位 $-1$$-1$ 的歧义。

例子与边界

$\gcd(30,18)=6$$gcd(30,18)=6$，且 $6=2\cdot30-3\cdot18$$6=2\cdot 30-3\cdot 18$。$\gcd(0,0)$$gcd(0,0)$ 常留作未定义，某些计算库约定为零，使用时需说明。由 $d\mid a,b$$d\mid a,b$ 不能只凭数值最大性证明 $d$$d$ 是 gcd，还需验证所有公共因子都整除 $d$$d$。Bézout 表示在整数和 PID 中成立，在一般 UFD 中未必成立；例如 $x,y$$x,y$ 在 $F[x,y]$$F[x,y]$ 中 gcd 为 $1$$1$，但不存在 $f x+g y=1$$fx+gy=1$。互素不表示两个数都是素数。

推论与应用

gcd 控制约分、模逆、线性丢番图方程、CRT 与欧几里得算法。

参考资料

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 1, greatest common divisors and Bézout identity。
• Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 1, gcd and relatively prime integers。