欧几里得算法证明

在证明之前先看一个说明:

对于两个数i=md,j=nd.

i、j的最大公约数是d的充要条件是:m和n互质。

再看另一个说明:

如果m和n互质,那么(m-kn)和n也互质。

这个可以用反正法:

假设(m-kn)和n不互质,那么存在一个因子e,使得(m-kn)=en。

那么m=(k+e)n,这与m、n互质的题目条件违背,所以假设不成立。

则(m-kn)和n也互质。

算法的步骤1,显然是成立的,因为这就是最大公约数的定义。

算法的步骤2:

其实算法证明的目标是r=i%j != 0时,gcd(i,j)=gcd(j,r)。

根据已知条件,设d是i、j的最大公约数,则

i=md,j=nd,其中m、n是互质的。(如果m、n不互质,d就不是最大公约数)

(现在要找的是gcd(j,r)的最大公约是也是d,那么就要用d去表示r,证明这个表达式的系数和n互质,那么d就是r和j的最大公约数)

接着上面的说,由于r=i%j,则i=kj+r其中k>=1,k=[m/n],带入上面的等式:

md=kndr,所以r=(m-kn)d,又因为j=nd,n和(m-kn)互质,所以d是j、r的最大公约数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注