最大公约数

最大公因数中的“最大”按整除公理库整除Divisibility存在整数倍关系时定义的二元关系。偏序理解，而不是只按数值大小：它整除两个数，并被任何其他公因数整除；取正号则消除了单位 $-1$ 带来的歧义。Bézout 形式又表明 gcd 是所有整数线性组合 $ax+by$ 中最小的正元素，于是约数描述与理想生成描述在整数中完全一致。

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

Euclidean 算法不仅给出 gcd，也能恢复 Bézout 系数。对 $662$ 与 $414$，有

所以 $gcd(662,414)=2$；回代得到

若把两个输入同时乘以非零整数 $c$，则 gcd 的绝对值也乘以 $|c|$；但在一般整环中只能说 gcd 在相差一个单位的意义下唯一，不能依赖整数的大小顺序来选代表元。

gcd 控制约分、模逆、线性丢番图方程、CRT 与欧几里得算法。Euclid 算法公理库整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。有效计算 gcd 和 Bézout 系数，进而求模逆、化简分数和解线性丢番图方程。gcd 条件控制 中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers两两互素模数下的同余方程组在模其乘积意义下有唯一解。 的兼容性，也区分互素、多项式公因子与主理想结构。