欧几里得算法 · aiwiki.page

欧几里得算法是一种求两个整数的最大公约数（GCD）的算法。在这两个整数不同时为零的前提下，最大公约数就是能够同时整除它们的最大正整数。该算法反复进行带余除法，直到余数为零；最后一个非零余数就是所求的结果。这一方法是数论中的基本方法，也可推广到多项式及其他代数结构。它不需要对输入的数进行质因数分解，就能求出最大公约数。(cs.drexel.edu)

历史表述

这一算法以欧几里得命名，他在《几何原本》第七卷中介绍了这一过程。命题1讨论如何判定两个数互素，命题2则求出两个不互素的数的最大公度数。命题3将这一构造推广到三个数。古代的表述采用反复相减的方式，而非现代的除法记法：不断从较大的量中减去较小的量。带余除法则将多次这样的减法合并为一次运算。(mathcs.clarku.edu)

步骤与示例

对于满足 $a\geq b$ 的正整数，带余除法给出唯一确定的整数 $q$ 和 $r$ ，使得

a=qb+r,\qquad 0\leq r<b.

算法将 $(a,b)$ 替换为 $(b,r)$ ，并重复这一过程。当第二个分量变为零时，第一个分量就是最大公约数。这一规则既可以用迭代实现，也可以用递归实现。(cs.drexel.edu)

例如，将这一规则用于252和105，得到

\begin{aligned} 252&=2\cdot105+42,\\ 105&=2\cdot42+21,\\ 42&=2\cdot21+0. \end{aligned}

因此， $\gcd(252,105)=21$ 。各步的商分别为2、2和2，最后一个非零余数为21。

对于不同时为零的非负输入，可以用以下简洁的伪代码表示：

gcd(a, b):
    while b ≠ 0:
        r ← a mod b
        a ← b
        b ← r
    return a

这里的 mod 表示非负余数。临时变量用于在每次更新时保留原有值。这个循环也能处理 $a<b$ 的情况：第一次迭代会交换两个输入的角色。(mosullivan.sdsu.edu)

正确性与终止性

核心恒等式为

\gcd(a,b)=\gcd(b,a-qb).

这一恒等式的数学证明基于整除关系。 $a$ 和 $b$ 的每个公约数都能整除 $a-qb$ 。反过来， $b$ 和 $a-qb$ 的每个公约数都能整除它们的组合 $(a-qb)+qb=a$ 。因此，这两对数具有完全相同的公约数。(mosullivan.sdsu.edu)

保持不变的最大公约数是一个循环不变量。与此同时，依次得到的非零余数构成严格递减的正整数序列，因此这一过程必然终止。终止时，数对为 $(d,0)$ ，其最大公约数为 $d$ 。这两个性质共同保证了返回值的正确性。(mosullivan.sdsu.edu)

扩展算法与应用

扩展欧几里得算法还会求出满足贝祖等式的整数 $x$ 和 $y$ ：

ax+by=\gcd(a,b).

每个余数都是原始输入的整数系数线性组合。在除法过程中跟踪这些系数，或在计算结束后沿各个等式反向回代，都能得到所需的系数。(cs.drexel.edu)

对于上述示例，

21=105-2\cdot42 =105-2(252-2\cdot105) =-2\cdot252+5\cdot105.

因此， $x=-2$ ， $y=5$ 。

这一扩展算法可以求解线性丢番图方程。当 $a,b$ 不同时为零时，方程 $ax+by=c$ 有整数解，当且仅当 $\gcd(a,b)$ 整除 $c$ 。只要这一条件成立，将贝祖系数乘以 $c/\gcd(a,b)$ ，就能得到一组解。(web.cs.miami.edu)

在模算术中，若 $\gcd(a,m)=1$ ，则由 $ax+my=1$ 可得 $ax\equiv1\pmod m$ 。因此， $x$ 代表 $a$ 的模乘法逆元。这样的逆元存在，当且仅当 $a$ 与 $m$ 互素。(mosullivan.sdsu.edu)

效率与连分数

算法的计算复杂性取决于计数的是除法次数，还是单个位运算的次数。对于正整数输入，除法次数为 $O(\log\min(a,b))$ ，这里使用了大O记号。相邻的斐波那契数列中的数，相对于其大小，会产生特别长的余数链：连续的除法大体上是沿斐波那契递推关系逆向进行。因此，位数不超过 $n$ 的输入需要 $O(n)$ 次除法。(sites.math.rutgers.edu)

这并不意味着运行时间与输入的位数成线性关系。大整数除法本身就需要多次运算。如果采用一种简单的分析方式，将每次除法的耗时计为 $O(n^2)$ ，便可得到 $O(n^3)$ 的上界，不过这一上界并不紧；更先进的最大公约数算法能够达到显著更好的位复杂度。(sites.math.rutgers.edu)

依次得到的商还给出了有理数 $a/b$ 的有限连分数展开。对于上述示例，

\frac{252}{105} =2+\frac{1}{2+\frac12} =[2;2,2].

因此，同一套除法步骤既给出了公约数，也给出了连分数表示。(sites.math.rutgers.edu)

代数推广

对于域（数学）上的多项式，除法的形式为

f=qg+r, \qquad r=0\ \text{或}\ \deg r<\deg g.

将 $(f,g)$ 替换为 $(g,r)$ 不会改变公约式，而次数的递减保证了算法终止。最后一个非零余式就是一个多项式最大公约式；它在相差一个非零常数因子的意义下唯一，通常将其规范化，使首项系数为1。(singacom.uva.es)

在抽象代数中，欧几里得整环是一种允许进行带余除法的整环，其中余数的某种以非负整数表示的大小度量会递减。这为推广后的算法提供了所需的终止机制。域上的多项式环就是这样的例子，其大小度量为多项式的次数。(singacom.uva.es)