第五章：整除性与最大公因数（2）

欧几里得算法#

求两个数的最大公因数的最有效方法是欧几里得算法，这是由直到余数为零的一系列带余除法组成的。在叙述一般方法前，我们用个例子来说明：
我们计算$gcd(36,132)$，第一步是$132$ 除以$36$ 得商$3$ 与余数$24$。我们将此记作

$132 = 3·36 +24$

第二步是取$36$，用前一步的余数$24$ 除以$36$ 得

$36 = 1·24 +12$

下一步，用$12$ 除以$24$ 求得余数$0$

$24 = 2·12 + 0$

欧几里得算法说明当得到余数$0$ 时，则前一步的余数就是最初两个数的最大公因数，所以在这种情况我们求得$gcd(132,36)=12$
注意如何在每一步用数$A$ 除以$B$ 得到商$Q$ 和余数$R$，换句话说，

$A = Q·B +R$

然后在下一步用数$B$ 与$R$ 代替原来的 $A$ 与$B$，继续此过程直到得到余数$0$ 为止。此时，前一步的余数$R$ 就是最初两个数的最大公因数。

欧几里得算法：要计算两个数$a$ 与$b$ 的最大公因数，先令$r_{-1}=a,r_0=b$，然后计算相继的商和余数

$r_{i-1}=q_{i-1}·r_{i}+r_{i-1}(i = 0,1,2,...)$

直到某余数$r_{n+1}$ 为$0$。最后的非零余数$r_n$ 就是$a$ 与$b$ 的最大公因数

本作品采用《CC 协议》，转载必须注明作者和本文链接