数论中的辗转相除法的简单理解

大家好，欢迎来到IT知识分享网。

首先考虑一下350和80两个数之间的最大公约数。

我们看的出来，最大公约数是10。

通过辗转相除法如何把这个最大公约数求出来呢？

首先把350除以80，得到商4，余数30。

接下来以原来的除数80作为被除数，余数30作为除数再作除法，得到商2，余数20。

第三次按同样的方法，以上次的除数30作为被除数，余数20作为除数，得商1，余数10。

再以20作为被除数，10作为除数，得商2，余数为0。

辗转相除法到此结束，得到350和80两个数的最大公约数是10。

这个过程其实非常简单，就是不停地把上一次除法中的除数变为被除数，余数变为除数，一直到除法得到的余数变成0为止，最后一次除法运算中的除数就是最大公约数。

四次除法过程如下：

图1

对于这个辗转相除法的理解，可能会存在如下两个困难：

1：为什么余数中会包含最大公约数？

2：这样得到的结果为什么就是最大公约数呢？

首先解释第一点。

因为我们首先假设两个数字间存在最大公约数k，并假设第一个数字比第二个数字大。

那么，我们就可以假设第一个数字包含a个k，即ak；第二个数字是bk。

作第一次除法，就相当于把ak减去若干个(就是商)bk，我们假设是C个，也就是

ak-Cbk，当然，这里a>cb。那么，是不是还剩下a-Cb个k?也就是余数也是最大公约数k的倍数。这一点最好的理解方法就是，被除数是最大公约数的倍数，除数也是，所以它们的差就像是用100个3减去80个3，自然也是最大公约数的倍数。

然后是第二点。

从图1看出，最后一次除法的除数其实就是最大公约数，也刚好除尽。

第一次除法，得到的余数中包含的最大公约数的数量（30，也就是3个10）肯定小于除数的数量（8个10），第二次的余数则是2个10，第三次就是1个10，第四次则除尽。由此可以看到，每次除法，得到的余数最少要比除数中包含的最大公约数的倍数要减少1倍，这样辗转相除下去，最后的余数必然只剩下一个最大公约数。如果剩下的数字m比我们认为的最大公约数k大的时候被除尽，则最大公约数就是m。

下面从理论上证明第一点：
借用一位知乎网友的证明。

首先将被除数命名为A，将除数命为B，将二者的商命名为C，将余数命名为D。于是原式就可以转化为： A=B⋅C+D 。
接下来假设被除数A和除数B拥有共同的因数k，那么可以得到： A=a⋅k,B=b⋅k
通过式子 A=B⋅C+D 可得：

D=A−B⋅C

D=a⋅k−b⋅k×C

提取公因子k后可得

D=k(a−b×C)

而括号中的 a−b×C 一定是一个整数，所以可以得到， 当被除数和除数拥有同样因子的情况下，余数也一定拥有相同的因子。

再证明第二点：

证明：反证法，我们以104，40辗转举例子 容易理解。假设d是104和40的非最大公约数，假设k为104和40的最大公约数 ，——>d<k。

根据上述传递性，d=(104,40)=(40,24)=(24,16)=(16,8),(16,8）=8这个是公认的。而根据假设，k=（104,40)=…..=(16,8) >8，而（16,8) 最大的公约数就是除数本身8。k不可能再大于8了，所以矛盾，故不存在k>b。所以这么辗转，得到的就是最大公约数。