最大公约数

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

$gcd(30,18)=6$，可用两步核对：$6$ 同时整除 $30,18$；任意公约数又都整除整数线性组合 $2\cdot 30-3\cdot 18=6$。这就验证了定义中的两个方向。

若两个输入都为零，每个正整数都是公约数，不存在最大的正公约数，因此上面的正值定义将这一对输入排除。将 gcd 扩展为非负值的常用约定是 $gcd(0,0)=0$，此时每个公约数仍整除它。

整数中的 gcd 同时具有 Bézout 表示，但这两件事在一般整环中可以分开。例如域 $F$ 上的 $F[x,y]$ 中，$x,y$ 的 gcd 为 $1$，却不存在多项式 $f,g$ 使 $fx+gy=1$：把 $x=y=0$ 代入，左边为零，右边为一。

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

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

回代式同时给出两项用途：它证实任何公约数都必须整除 $2$，也给出了使整数线性组合等于 $2$ 的一组系数。若将两个输入同时乘以非零整数 $c$，公约数关系随之缩放，得到 $gcd(ca,cb)=|c|gcd(a,b)$。

Euclid 算法公理库整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。算出的 Bézout 系数可以直接转成解的证书。若 $m\ge 2$、$gcd(a,m)=1$ 且 $ax+my=1$，模 $m$ 后得到 $ax\equiv 1$，所以 $x$ 就是 $a$ 的模逆。对不全为零的整数 $a,b$，$au+bv=c$ 有整数解当且仅当 $gcd(a,b)\mid c$：必要性来自整除，充分性来自把 Bézout 等式乘以 $c/gcd(a,b)$。

同一个整除条件也出现在中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers用最大公因数判定一般联立同余的相容性，并构造模最小公倍数唯一的解。中。两个同余 $x\equiv r(\mathrm{mod}m)$、$x\equiv s(\mathrm{mod}n)$ 能同时满足，当且仅当 $gcd(m,n)\mid (r-s)$。模数互素只是让这一兼容条件对所有余数自动成立。