整数欧几里得算法

用较小余数替换较大数不会改变公共因子，却使规模严格下降。终止性来自自然数不能无限下降，回代则保留每个余数对原输入的线性表达。Euclid 算法不断用余数替换较大的数，因为共同约数在这一步完全不变：$d$ 同时整除 $a,b$ 当且仅当它同时整除 $b,a-qb$。余数严格变小保证过程终止，最后一个非零余数便捕获全部共同约数中的最大者。它把一个全局的约数问题压缩成局部除法序列。

计算 $gcd(252,105)$：

故最大公因数为 $21$。倒推得到 $21=5\cdot 105-2\cdot 252$，同时给出 Bézout 系数；扩展算法也因此能求$a$ 模 $n$ 的逆，而逆存在当且仅当 $gcd(a,n)=1$。若输入含负数，算法通常先取绝对值并在最后调整符号，取非负gcd；$gcd(0,0)$ 的约定需单独说明。还要注意，除法步数的对数界不表示所有大整数实现都有线性时间，实际复杂度也包含算术操作成本；算法成立的核心是不变量与良基下降，而不是“分治”这个名称。

欧几里得算法用于约分、模逆、CRT 拼接、RSA 密钥运算和有理重构。算法计算 最大公因数公理库最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。，扩展版本还构造 Bézout 等式，从而求模逆、解线性同余并支撑 整数中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers两两互素模数下的同余方程组在模其乘积意义下有唯一解。。其“带余除法 + 范数下降”模式推广到 Euclid 整环公理库欧几里得整环Euclidean domain带有允许带余除法并严格下降的欧几里得函数的整环。 和多项式环。