主题
Search

欧几里得算法

下载 Mathematica 笔记本下载 Wolfram 笔记本

欧几里得算法，也称为欧几里得辗转相除法，是用于查找两个数 a 和 b 的最大公约数的算法。该算法也可以为比整数 Z 更一般的环定义。甚至存在不是欧几里得环的主环，但可以在其中定义等效于欧几里得算法的算法。有理数算法在欧几里得《几何原本》的第七卷中给出。实数算法出现在第十卷中，使其成为最早的整数关系算法示例（Ferguson等人1999）。

欧几里得算法是一个P问题的例子，其时间复杂度受输入值长度的二次函数限制（Bach 和 Shallit 1996）。

设 a=bq+r，然后找到一个数 u，它整除 a 和 b （因此 a=su 和 b=tu），那么 u 也整除 r，因为

r=a-bq=su-qtu=(s-qt)u.
(1)

类似地，找到一个数 v，它整除 b 和 r （因此 b=s^'v 和 r=t^'v），那么 v 也整除 a，因为

a=bq+r=s^'vq+t^'v=(s^'q+t^')v.
(2)

因此，a 和 b 的每个公约数也是 b 和 r 的公约数，因此该过程可以迭代如下

q_1=|_a/b_| a=bq_1+r_1 r_1=a-bq_1 ; q_2=|_b/(r_1)_| b=q_2r_1+r_2 r_2=b-q_2r_1 ; q_3=|_(r_1)/(r_2)_| r_1=q_3r_2+r_3 r_3=r_1-q_3r_2 ; q_4=|_(r_2)/(r_3)_| r_2=q_4r_3+r_4 r_4=r_2-q_4r_3 ; q_n=|_(r_(n-2))/(r_(n-1))_| r_(n-2)=q_nr_(n-1)+r_n r_n=r_(n-2) ; -q_nr_(n-1); q_(n+1)=|_(r_(n-1))/(r_n)_| r_(n-1)=q_(n+1)r_n+0 r_n=r_(n-1)/q_(n+1)
(3)

对于整数，当 q_(n+1) 恰好整除 r_(n-1) 时，算法终止，此时 r_n 对应于 a 和 b 的最大公约数，GCD(a,b)=r_n。对于实数，该算法产生精确关系或近似关系的无限序列（Ferguson等人1999）。

欧几里得算法的一个重要结果是找到整数 x 和 y，使得

ax+by=GCD(a,b).
(4)

这可以通过从 r_n 的方程开始，从前一个方程代入 r_(n-1)，并向上遍历方程来完成。

请注意，r_i 只是余数，因此可以通过手动重复计算以两个感兴趣的数字（较大的数字写在前面）开始的连续项的余数来轻松应用该算法。例如，考虑将该算法应用于 (a,b)=(42,30)。这给出 42, 30, 12, 6, 0，因此 GCD(42,30)=6。类似地，将该算法应用于 (144, 55) 得到 144, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0，因此 GCD(144,55)=1，并且 144 和 55 是互质的。

一个简洁的 Wolfram 语言 实现可以如下给出。

  Remainder[a_, b_] := Mod[a, b]
  Remainder[a_, 0] := 0
  EuclideanAlgorithmGCD[a_, b_] := FixedPointList[
    {Last[#], Remainder @@ #}&, {a, b}][[-3, 1]]

拉梅证明，对于小于 n 的两个数，到达最大公约数所需的步数为

steps<=(lnn)/(lnphi)+(lnsqrt(5))/(lnphi)
(5)

其中 phi 是黄金比例。在数值上，拉梅的表达式评估为

steps<=4.785log_(10)n+1.6723,
(6)

对于 n>=1，总是小于等于较小数的位数的 <=5 倍（Wells 1986，第 59 页）。正如拉梅定理所示，最坏情况发生在将算法应用于两个连续的斐波那契数时。海尔布朗证明，对于所有对 (n,b)，其中 b<n，平均步数为 12ln2/pi^2lnn=0.843lnn。克罗内克证明，算法的最短应用使用最小绝对余数。获得的商的分布如下表所示（Wagon 1991）。

商%
141.5
217.0
39.3

设 T(m,n) 为使用欧几里得算法计算 GCD(m,n) 所需的除法次数，并定义 T(m,0)=0 如果 m>=0。那么函数 T(m,n) 由递推关系给出

T(m,n)={1+T(n,m mod n) for m>=n; 1+T(n,m) for m<n.
(7)

对于 0<=m<n，制表此函数得到

0 ; 0 1 ; 0 1 2 ; 0 1 1 2 ; 0 1 2 3 2 ; 0 1 1 1 2 2
(8)

（OEIS A051010）。给定 n=1、2、3、... 的最大步数为 1、2、2、3、2、3、4、3、3、4、4、5、... （OEIS A034883）。

EuclideanAlgorithmT

考虑函数

T(n)=1/nsum_(0<=m<n)T(m,n)
(9)

给出当 n 固定且 m 随机选择时的平均步数（Knuth 1998，第 344 页和 353-357 页）。T(n) 的前几个值为 0, 1/2, 1, 1, 8/5, 7/6, 13/7, 7/4, ... （OEIS A051011 和 A051012）。Norton (1990) 表明

T(n)=(12ln2)/(pi^2)[lnn-sum_(d|n)(Lambda(d))/d]+C+1/nsum_(d|n)phi(d)O(d^(-1/6+epsilon)),
(10)

其中 Lambda(d) 是芒戈尔特函数，C 是波特常数（Knuth 1998，第 355-356 页）。

EuclideanAlgorithmTau

相关函数

tau(n)=1/(phi(n))sum_(0<=m<n; GCD(m,n)=1)T(m,n)
(11)

其中 phi(n) 是欧拉总计函数，给出当 n 固定且 m 是与 n 互质的随机数时的平均除法次数。Porter (1975) 表明

tau(n)=(12ln2)/(pi^2)lnn+C+O(n^(-1/6)+epsilon)
(12)

（Knuth 1998，第 354-355 页）。

最后，定义

A(N)=1/(N^2)sum_(1<=m<=N; 1<=n<=N)T(m,n),
(13)

作为当 m 和 n 都在 [1,N] 中随机选择时的平均除法次数。Norton (1990) 证明

A(N)=(12ln2)/(pi^2)[lnN-1/2+6/(pi^2)zeta^'(2)]+C-1/2+O(N^(-1/6+epsilon)),
(14)

其中 zeta^'(z) 是黎曼 zeta 函数的导数。

存在 21 个二次域，其中存在欧几里得算法（Inkeri 1947，Barnes 和 Swinnerton-Dyer 1952）。

有关更多详细信息，请参见 Uspensky 和 Heaslet (1939) 以及 Knuth (1998)。

尽管为推广算法以找到 n>=3 个变量之间的整数关系做出了各种尝试，但在Ferguson-Forcade 算法被发现之前，没有一个成功（Ferguson等人1999）。现在已经发现了其他几种整数关系算法。

另请参阅

Blankinship 算法，欧几里得环，Ferguson-Forcade 算法，半 GCD，整数关系，二次域 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

参考文献

Bach, E. 和 Shallit, J. 算法数论，第 1 卷：高效算法。 Cambridge, MA: MIT Press, 1996.Barnes, E. S. 和 Swinnerton-Dyer, H. P. F. "二元二次型的非齐次极小值。I." Acta Math 87, 259-323, 1952.Chabert, J.-L. (Ed.). "欧几里得算法。" 第 4 章，算法的历史：从卵石到微芯片。 New York: Springer-Verlag, pp. 113-138, 1999.Cohen, H. 计算代数数论课程。 New York: Springer-Verlag, 1993.Courant, R. 和 Robbins, H. "欧几里得算法。" 第 2.4 节，第 1 章的补充，什么是数学？：思想和方法的初等方法，第 2 版。 Oxford, England: Oxford University Press, pp. 42-51, 1996.Dunham, W. 天才之旅：数学的伟大定理。 New York: Wiley, pp. 69-70, 1990.Ferguson, H. R. P.; Bailey, D. H.; 和 Arno, S. "PSLQ 的分析，一种整数关系查找算法。" Math. Comput. 68, 351-369, 1999.Finch, S. R. "波特-汉斯利常数。" 第 2.18 节，数学常数。 Cambridge, England: Cambridge University Press, pp. 156-160, 2003.Inkeri, K. "关于二次数域中的欧几里得算法。" Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.Knuth, D. E. 计算机程序设计艺术，第 1 卷：基本算法，第 3 版。 Reading, MA: Addison-Wesley, 1997.Knuth, D. E. 计算机程序设计艺术，第 2 卷：半数值算法，第 3 版。 Reading, MA: Addison-Wesley, 1998.Motzkin, T. "欧几里得算法。" Bull. Amer. Math. Soc. 55, 1142-1146, 1949.Nagell, T. "欧几里得算法。" 第 7 节，数论导论。 New York: Wiley, pp. 21-23, 1951.Norton, G. H. "关于欧几里得算法的渐近分析。" J. Symb. Comput. 10, 53-58, 1990.Porter, J. W. "关于海尔布朗定理。" Mathematika 22, 20-28, 1975.Séroul, R. "欧几里得除法" 和 "欧几里得算法。" 第 2.1 节和 8.1 节，程序员数学。 Berlin: Springer-Verlag, pp. 5 和 169-161, 2000.Sloane, N. J. A. 序列 A034883, A051010, A051011, 和 A051012，在 "整数序列在线百科全书" 中。Uspensky, J. V. 和 Heaslet, M. A. 初等数论。 New York: McGraw-Hill, 1939.Wagon, S. "古老而现代的欧几里得算法" 和 "扩展欧几里得算法。" 第 8.1 节和 8.2 节，Mathematica 在行动。 New York: W. H. Freeman, pp. 247-252 和 252-256, 1991.Wells, D. 好奇和有趣的数字企鹅词典。 Middlesex, England: Penguin Books, p. 59, 1986.

请引用为

Weisstein, Eric W. "欧几里得算法。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/EuclideanAlgorithm.html

学科分类