欧几里得——辗转相除法

个人粗浅证明:设最大公约数为k,则m=ak,n=bk,每次取余都会相当于不大于2n的m’-n=(a’-b)k(假设m>=n)。显然最后总会得到结果的,因为最大公约数至少会是1。此外,不可能会出现r=ck,其中c>=2,m%n=0而退出循环,因为一但如此,m=n+r=b’ck+ck=(b+c)k,最大公约数会变成ck,而不再会是k了,与题设矛盾。

程序:

辗转相除法动画演示:

辗转相除法的演示动画:两条线段分别表示252和105,其中每一段表示21。动画演示了循环从大数中减去小数,直到其中一段的长度为0,此时剩下的一条线段的长度就是252和105的最大公约数。

Wikipedia证明:

算法描述

计算过程

辗转相除法是一种递归算法,每一步计算的输出值就是下一步计算时的输入值。[21]k表示步骤数(从0开始计数),算法的计算过程如下。

每一步的输入是都是前两次计算的余数rk−1rk−2。因为每一步计算出的余数都在不断减小,所以,rk−1小于rk−2。在第k步中,算法计算出满足以下等式的qk余数 rk

rk−2 = qk rk−1 + rk

其中rk < rk−1。也就是rk−2要不断减去rk−1直到比rk−1小。

在第一步计算时(k = 0),设r−2r−1分别等于ab,第2步(此时k = 1)时计算r−1(即b)和r0(第一步计算产生的余数)相除产生的商和余数,以此类推。整个算法可以用如下等式表示:

a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3

如果输入参数因为a < b,所以ab相除得到的商q0等于0,余数r0等于a。所以在运算的每一步中得出的余数一定小于上一步计算的余数(rk一定小于rk−1)。

由于每一步的余数都在减小并且不为负数(请求严谨证明),必然存在第N步时rN等于0,使算法终止,[20]rN−1 就是ab的最大公约数。其中N不可能无穷大,因为在r0和0之间只有有限个自然数。

正确性的证明

辗转相除法的正确性可以用两步来证明。[21]首先,算法的最终结果rN−1同时整除ab。因为它是一个公约数,所以必然小于或者等于最大公约数g。然后,任何ab的公约数都能整除rN−1。所以g一定小于或等于rN−1。两个不等式只在rN−1 = g是同时成立。具体证明如下:

  1. 证明rN−1同时整除ab
    因为余数rN是0,rN−1能够整除rN−2

    rN−2 = qN rN−1
    因为rN−1能够整除rN−2,所以也能够整除rN−3

    rN−3 = qN−1 rN−2 + rN−1
    同理可证rN−1可以整除所有之前步骤的余数,包括ab,即rN−1ab的公约数,rN−1 ≤ g
  2. 证明任何整除ab的自然数g(也就是ab的公约数)都能整除rN-1
    根据定义,ab可以写成g的倍数:a = mgb = ng,其中mn是自然数。因为r0 = a − q0b = mg − q0ng = (m − q0n)g,所以g整除r0。同理可证g整除每个余数r1r2……rN-1。所以,最大公约数g一定整除rN−1,因而g ≤ rN−1

因为第一步的证明告诉我们rN−1 ≤ g,所以g = rN−1。即:

g = GCD(a, b) = GCD(b, r0) = GCD(r0, r1) = … = GCD(rN−2, rN−1) = rN−1

举例

算法的演示动画。最初的绿色矩形的长和宽分别是a = 1071、b = 462,从中不断铺上462×462的正方形直到剩下部分面积是462×147;然后再铺上147×147的正方形直至剩下21×147的面积;最后,铺上21×21的正方形时,绿色部分就没有了。即21是1071和462的最大公约数.

例如,计算a = 1071和b = 462的最大公约数的过程如下:从1071中不断减去462直到小于462(可以减2次,即商q0 = 2),余数是147:

1071 = 2 × 462 + 147.

然后从462中不断减去147直到小于147(可以减3次,即q1 = 3),余数是21:

462 = 3 × 147 + 21.

再从147中不断减去21直到小于21(可以减7次,即q2 = 7),没有余数:

147 = 7 × 21 + 0.

此时,余数是0,所以1071和462的最大公约数是21,这和用素因数分解得出的结果相同(见上文)用表格表示如下:

步骤数 算式 商和余数
0 1071 = 462 q0 + r0 q0 = 2、r0 = 147
1 462 = 147 q1 + r1 q1 = 3、r1 = 21
2 147 = 21 q2 + r2 q2 = 7、r2 = 0(算法终止)

 

未经允许不得转载:TacuLee » 欧几里得——辗转相除法

赞 (22)

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. cheetah输入我一针见血的评论回复
  2. bloodthirstylalalalalalalalalalalalalalala回复