第五章：整除性与最大公因数（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 协议》，转载必须注明作者和本文链接