欧几里得算法与扩展欧几里得算法

老王

欧几里得算法

寻找两个整数最大公约数的一个方法是找出两个整数的所有正公约数，然后取其中最大的那个。例如，求                              ，24和36的正公约数包括1、2、3、4、6和12，因此 。如果两个整数都比较大，这种方法非常低效。

另一个寻找两个整数最大公约数的方法是利用这两个整数的素因子分解式。假设两个正整数 和 的素因子分解式分别为 ，其中 这些素因子应该出现在每个素因子分解式中，必要时以0指数出现，每个指数都是非负整数。计算公式为 ，也就是将两个整数共有的素因子中指数较小的各项相乘。

例如，求 ，120和500的素因子分解式分别为 和 ， 。

两个正整数 和 的最小公倍数，同样可以通过 和 的素因子分解式来进行计算。计算公式为 。注意，一个整数有但另一个整数没有的素因子，另一个整数的相应素因子应该以0指数表示而不可以忽略。

关于最大公约数和最小公倍数，可以换一种说法。还是120和500的例子， 。求 ，就是将两个整数共有的素因子（交集）相乘的结果，也就是 ；求 ，就是将两个整数共有的和各自独有的素因子（并集）相乘的结果，也就是 。

最大公约数和最小公倍数的关系。设 和 均为正整数，那么 。

欧几里得算法，又称辗转相除法，是寻找两个整数最大公约数的算法。算法原理：两个整数的最大公约数等于其中较小的整数和较大的整数除以较小的整数所得的余数的最大公约数。设 ，令 ，其中 均为整数，那么 ，或者说 。不断应用上述等式，每一次都会缩小较大的数，直到余数为0，所剩下的还没有变成0的那个数就是两个整数的最大公约数。

实际上欧几里得算法的原理和最大公约数的重要性质(4)是对应的。欧几里得算法在处理大整数时非常高效，需要的步骤不会超过较小整数的位数（十进制）的5倍。

例如，计算662和414的最大公约数的过程如下：

(1)   ；

(2)   ；

(3)   ；

(4)   ；

(5)   。

余数已经为0，另一个数2就是最大公约数，因此 。

贝祖定理与扩展欧几里得算法

两个整数的最大公约数可以通过两数的整数倍相加来表示，例如上面的例子， 。这个结论称为贝祖定理(也称裴蜀定理)，给定两个正整数 和 ，必然存在整数 和 使得 ，也就是最大公约数可以表示为 和 的线性和的形式。上述等式称为贝祖恒等式，整数s和t称为贝祖系数。

关于如何找出贝祖系数，有两种方法。第一种方法是首先执行欧几里得算法，然后再做一次反向处理；第二种方法是直接使用扩展欧几里得算法。

通过对欧几里得算法的除法步骤做反向处理得到贝祖系数的过程如下：

由步骤(4)可得 ，

由步骤(3)可得 ，推出 ，

由步骤(2)可得 ，推出 ，

由步骤(1)可得 ，推出 ，

因此， 。

扩展欧几里得算法是欧几里得算法的扩展，在欧几里得算法中，仅仅利用了每步带余除法所得的余数，扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时还能得到一对贝祖系数。

为了使用扩展欧几里得算法，设 ，并令 ，其中 ， 是做带余除法时的商。

还是以 为例，通过扩展欧几里得算法计算贝祖系数的过程如下：

	商	余数
1	662÷414＝1	248
2	414÷248＝1	166
3	248÷166＝1	82
4	166÷82＝2	2
5	82÷2＝41	0

当余数为0时计算结束，上一步的贝祖系数即满足 。

扩展欧几里得算法是一种自验证算法，最后一步得到的 和 分别乘以 后恰为 和 ，可以以此来验证计算结果是否正确。注意，其中一个贝祖系数极有可能是负整数，如果是负整数则取绝对值。即 。