求最大公因数算法

2020年3月25日 · 11 views · 

辗转相除法

求 $gcd(a,b)$ 时,令 $r=a/b , a=b , b=r$ 。重复以上步骤,直到 $r=0$ ,此时 $b$ 即为 $gcd(a,b)$ 。

证明辗转相除法

要证明它,就要证明以下三点:

  • 最后的b为a与b的公因数
  • 最后的b为a与b的公因数中最大的
  • 为什么最后余数一定会等于0

证明结果为a与b的公因数

设对于某对(a,b),有以下四步。

$a ÷ b = q_1 … r_1$

$b ÷ r_1 = q_2 … r_2$

$r_1 ÷ r_2 = q_3 … r_3$

$r_2 ÷ r_3 = q_4 … 0$

反过来,就是

$a=q_1b+r_1$

$b=q_2r_1+r_2$

$r_1=q_3r_2+r_3$

$r_2=q_4r_3+0$

从下往上看,$r_2,r_1,b,a$都是$r_3$的倍数,所以$r_3$是$a,b$的公因数。

证明结果为最大的公因数

还是上面的一组式子,从上往下看。设d为a与b任意的公因数。则推导出:

$r_1,r_2,r_3$也是$d$的倍数

所以$r_3$是a与b任何因数的倍数,所以$r_3$是最大公因数。

证明余数最后一定会等于0

显然,每一步的余数都会比除数小,所以它是个递减序列,最后一定会减为0。

更相减损术

如果两个数是偶数,则用2约分并记录次数。然后不停的用大的数减去小的数,直到减数和差相等,差乘上一开始约掉的2则是结果

stein算法

  • 如果$a==b$,则返回$a$
  • 如果a和b都是偶数,a和b都除以2,并记录个数。
  • 如果a和b是一奇一偶,把偶数除以2,奇数不变。
  • 如果a和b都是奇数,则$a=|a-b|/2$,$b=min(a,b)$。

返回

Steven's Website Copyright © 2020 Steven
Powerd by Wordpress & Theme by Steven
粤ICP备20028373号