欧几里得算法是一种求两个整数的最大公约数（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)