形式陈述

对整数 $a$$a$ 与非零 $b$$b$，除法算法给出唯一 $q,r$$q,r$，使

$$ a=bq+r, \qquad 0\le r<|b|. $$$$a=bq+r,0\le r<|b|.$$

且

$$ \gcd(a,b)=\gcd(b,r). $$$$gcd(a,b)=gcd(b,r).$$

反复用 $(a,b)\leftarrow(b,r)$$(a,b)\leftarrow (b,r)$，余数形成严格下降的非负整数列，必在有限步后到达零；最后一个非零余数即 $\gcd(a,b)$$gcd(a,b)$。把每个余数向前回代，可求整数 $x,y$$x,y$ 使 $ax+by=\gcd(a,b)$$ax+by=gcd(a,b)$，称扩展欧几里得算法。其位复杂度依实现而异，基本除法步数为 $O(\log\min(|a|,|b|))$$O(\log min(|a|,|b|))$。

直觉

用较小余数替换较大数不会改变公共因子，却使规模严格下降。终止性来自自然数不能无限下降，回代则保留每个余数对原输入的线性表达。

例子与边界

$252=105\cdot2+42$$252=105\cdot 2+42$，$105=42\cdot2+21$$105=42\cdot 2+21$，$42=21\cdot2$$42=21\cdot 2$，故 gcd 为 $21$$21$。扩展算法还能求 $a$$a$ 模 $n$$n$ 的逆：逆存在当且仅当 $\gcd(a,n)=1$$gcd(a,n)=1$。算法处理负输入时通常先取绝对值并在最后调整符号。除法步数的对数界不等于所有大整数实现都线性时间；算术操作成本也需计算。该算法不是依赖“分治”概念才成立，其核心是不变量与良基下降。

推论与应用

欧几里得算法用于约分、模逆、CRT 拼接、RSA 密钥运算和有理重构。

参考资料

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 1, Euclidean algorithm and continued remainders。
• Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 1, Euclidean and extended Euclidean algorithms。