[数论]辗转相除法求gcd的数学证明

在写证明过程之前,我们先回顾一下最大公约数gcd的欧几里得求法。

gcd,即最大公因数。为了书写方便,人们常习惯以gcd(a,b)表示a,b的最大公因数。那最小公倍数呢?我们知道若已知a,b,gcd(a,b),那么最小公倍数就自然等于a * b / gcd(a,b)。这里就不证明了。

我们接着看gcd,如何高效求gcd呢?目前最快的方法算是欧几里得算法了。

欧几里得算法其实很简单,已知a,b,其中a>b,求gcd(a,b)。

解:用b整除a,得到余数c,再用c整除b,得到余数d,再用d整除c,得到余数e……不断这样操作,最后直到没有余数为止。假设e再整除d,余数为0,则e为最大公因数。

列式子即为:

a = x1 * b + r1;

b = x2 * r1 + r2;

r1 = x3 * r2 + r3;

……

rn-1= xn+1 * rn + rn+1;

rn = xn+2 * rn+1 + 0;

若设a为r-1,b为r0,则通项公式即为rn-1 / rn = xn+1 rn + rn+1,最后一项为rn / rn+1 = xn+2 rn+1。

很容易理解,若某一步余数为0,则上一步的余数即为最大公约数。很容易证明该循环一定会终止,因为最坏的情况下a和b的最大公因数是1,那么任何一个数都是1的倍数,所以任何数取余1都为0,所以循环必会结束。

该算法历经千年,直到现在依然为求解gcd最高效的算法,gcd(a,b)最坏的情况下运算次数最多才是b位数的7位,这里就不详细介绍了。

那么为什么最后的结果就是最大公因数呢,接下来我们来证明一下。

假设g为gcd(a,b),即g为g,b的最大公因数,则带到上式记为rn = xn+2 * g,这个式子g必然为rn的因数。

那再带到上一个式子,rn-1 = xn+1 * rn + g,由于g既是rn的因数,又是g的因数,则g是rn-1的因数。

再带到上一个式子,rn-2 = xn * rn-1 + rn,由于g是rn-1,rn的因数,所以g必然是rn-2的因数。

……

最终带到第一组式子中,即g既是a的因数,也是b的因数。

那如何证明它是最大公因数呢?

我们假设h为a,b的任意因数,则h整除a,且h整除b,带到第一个式子,则h整除r1,再带到第2个式子,h整除r2,再带到第3个式子,h整除r3……直到倒数第二个式子,h整除rn+1,即h整除g由于最后一个式子余数为0,那么既然g为a,b的因数,h为g的因数,则h<=g,故g为gcd(a,b)。

证毕。


文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!