说说辗转相除法原理

今天我们来解释一下辗转相除法，相信大家都懂的这种方法。（不懂得自己去百度。）

现在解释一下这个方法背后的原理。

设定2个数: M, N（其中M >= N）

令c为M, N的最大公因数，

则可得

M = m * c  

N = n * c  

其中m,n为某整数，使得m * c 得 M， n * c 得 N。

可知，m、n互为质数————如果不是互为质数，c就不是最大公因数。

辗转相除法的第一步，

M / N = a ... L  

其实也可以理解为

L = (m - a * n) * c  

为什么呢？这就是简单的除法原理呀。不解释了，接着走。

辗转相除法的规则，就是用N和L继续往下求最大公因数了。

为什么这样做呢？因为N和L的最大公因数也是M和N的最大公因数。

为什么N和L的最大公因数也是M和N的最大公因数？

这就需要证明了。以下是这一步的证明。提前说一下，以下的证明，就是辗转相除法的原理的。辗转相除法，就是以下原理的递归实现。递归实现的意思，就是不断地算下去。

证明如下

已知

M = m * c  

N = n * c  

L = (m - a * n) * c  

其中m和n互质，所以c是M和N最大公因数。

如果m - a * n与n互质，那么N和L的最大公因数就是c了。

为什么？因为m - a * n 和 n没法再取出一个公因数来了。

那么怎么证明m - a * n与n互质呢？

反证法！

如果不是互质的，那么

m - a * n = x * d  

n = y * d  

那么

(m - a * n) + (a * n) = xd + a * (y * d) = (x + a*y) * d  

(m - a * n) + (a * n) = m  

s.t. m = (x + a*y) * d  

while n = y * d  

这么一来，m和n还叫互质吗？？

反证结束

前面已经说了，辗转相除法，就是以上证明了的原理的递归实现。