2.3　欧几里得算法

很多人在小学期间就接触过欧几里得算法（The Euclidean Algorithm）[8] ，它就是数学课本中的辗转相除法。它最早出现在欧几里得所著的《几何原本》中，书中不光介绍了平面几何和立体几何，还介绍了一些基础数论的知识，如整除性、素数、最大公约数、最小公倍数等。中国古代学者也发现了辗转相除法，如在《九章算术》中，作者就介绍了约分术。其原文是：“约分术日：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也。以等数约之。”大意是给定两个整数，如果它们都为偶数，则将它们减半后再计算；如果不是偶数，则用较大的数减去较小的数，然后将所得差与较小的数组合为一对新的数，再用大数减小数，反复相减直到差数与较小的数相等，这个等数就是最初两个数的最大公约数。

遗憾的是，《几何原本》中的数学知识有明确的概念及严格的推导过程和证明，《九章算术》则没有。因此后世也将辗转相除法称为欧几里得算法。

如果是两个整数，其中至少有一个非零整数，那么和的最大公约数（The Greatest Common Divisor，GCD)就是能同时除和的最大整数，记作。并且它们有几个性质，如果且，那么能整除就说明。如果，在除法定理中，。

那么如何找到呢?使用欧几里得算法。

1）设，并且。令，。通过除法定理，可求得：

2）如果，显然能整除，因此。如果，那么用除则得到整数和:

3）如果，显然能整除，因此。如果，那么用除则得到整数和。对于，可求得:

4）继续使用该除法过程直到余数等于0为止，最后一个非零余数就是最大公约数：

这是因为余数组成的递减序列是，不会包含大于的整数。对于，有。因此。

如果，那么。以下展示两个计算最大公约数的示例。

例2.3.1　计算。

解：

所以。

例2.3.2　计算。

解：

所以。

计算最大公约数的Python代码如下，该函数与math.gcd(a,b)结果相同。

 1  def gcd(a, b):
 2      if(b == 0):
 3          return abs(a)
 4      else:
 5          return gcd(b, a % b)

假设，，如果，那么就可以说是互素（Coprime）的。

现在设想一个问题，如果给定3个整数，需要在方程中找到所有的整数，应该如何运算呢？该方程也称不定方程或者丢番图方程（Diophantine Equation），值得注意的是，如果，则式子被称为齐次的（Homogeneous），反之，则称为非齐次的。

首先假设，那么。这个时候需要同除以，得到：

其中，，此时。下一步，可以将和两式联立，得到，，，有多组解。

假设，同样的，式子左右都同除以，得到：

值得注意的是，如果不能整除，那么方程无解。如果可以整除，那么式子就可以改写成，。接着使用欧几里得算法找到方程的解，方程的解等于，方程的解等于。

最后，联立和，得到解：

例2.3.3　找出式的所有解。

解：首先使用欧几里得算法计算得到最大公约数，发现7可以整除35 ，有解。接着式子同除以：

然后对式子使用欧几里得算法，得到:

，。而。因此最后得到解，其中。