整数欧几里得算法

算法每次换一对更小的数，却保留完整的共同约数信息。若 $d$ 整除 $a,b$，它也整除 $r=a-qb$；反过来，若 $d$ 整除 $b,r$，它也整除 $a=qb+r$。所以 $(a,b)$ 与 $(b,r)$ 的共同约数完全相同。

余数满足 $0\le r<|b|$，因此这种替换只能进行有限次。最终到达 $(g,0)$ 时，两数的共同约数就是 $g$ 的约数，最大者为 $|g|$。每条除法等式也保留着回去的路：从最后的 $g$ 逐步代回，就能把它写成原输入的整数线性组合。

计算 $gcd(252,105)$：

最后一个非零余数为 $21$。回代时先从第二式解出它，再用第一式消去 $42$：

这样既求得最大公因数，也得到 Bézout 系数。若原输入是 $-252,105$，则同一个等式写成 $21=2(-252)+5\cdot 105$；先对绝对值运行算法，再恢复输入符号即可。

零输入也与终止状态相接：$(a,0)$ 直接给出 $|a|$，$(0,b)$ 经一次替换到达 $(b,0)$。本条的输入约定排除了 $(0,0)$。

求出最大公因数后，将分子、分母同时除以它，就得到最简分数。扩展版本还能求模逆：若 $ax+ny=1$，模 $n$ 后便得到 $ax\equiv 1$，所以 $x$ 是 $a$ 的逆元；这样的等式存在恰好等价于 $gcd(a,n)=1$。

这些逆元用于解线性同余、构造整数中国剩余定理理路整数中国剩余定理Chinese remainder theorem for integers用最大公因数判定一般联立同余的相容性，并构造模最小公倍数唯一的解。中的坐标选择器，并参与 RSA 的指数计算。沿余数序列保留的线性关系还用于有理重构。把整数绝对值换成其他严格下降的量，同样的算法思路便推广到欧几里得整环理路欧几里得整环Euclidean domain带有允许带余除法并严格下降的欧几里得函数的整环。，包括域上的一元多项式环。

保留各次带余除法的商，还能得到原有理数的简单连分数理路简单连分数与收敛分数Simple continued fraction · Convergent · 简单连分数 · 收敛分数通过反复取整数部分与倒数，把实数写成简单连分数，并用收敛分数给出可证明的有理逼近误差。：上例的商依次为 $2,2,2$，因此 $252/105=[2;2,2]$。沿这串商逐步截断会得到收敛分数；把取整数部分与倒数的过程推广到无理数，就能进一步构造带有误差证书的有理逼近。