欧几里得算法:
考虑任意两个正整数a, b (a>b),求其最大公约数。
算法的步骤可概括为以下递归过程:
1. gcd(a, b) = gcd(b, a % b) 2. gcd(a, 0) = a
算法的正确性
有穷性:
由模运算的性质可知,$a\%b < b$, 所以在递归过程中,两个参数都严格递减。其中b必然降低到0。
正确性:
正确性的证明从两个面来进行:
1 . gcd(a, b) = gcd(b, a % b)
这一步的证明同样分为两点:
①. a, b的**最大公约数**d,是a%b(记为m)与b的**公约数**
记`gcd(a, b) = d`。
a和b可分别表示为
$a = k1 * d$
$b = k2 * d$
(易知,k1,k2互素
记`a % b = m`
存在整数k,使以下式子成立
$a = k * b + m$
则 $m = a - k * b = (k1 - k2 * k) * d$
得证
②. d是m与b的**最大**公约数
只需证明$k1-k2*k$ 与 $k2$ 互素即可
反证法:
若不互素
记
$k2 = p*t $ – a,
$k1-k2\*k = q\*t$ – b
a带入b得
$k1 - p * k * t = q* t$
=> $k1 = (p * k + q) * t$
此时k1与k2有公因数t,k1, k2不互素,与前述结论矛盾。
所以$k1-k2*k$ 与 $k2$ 互素
2 . 当一个参数为0时,另一个参数就是上一层a,b的最大公约数
考虑迭代过程中最后4个余数,分别为
0, r1, r2, r3 。
存在以下关系:
$r2 \% r1 = 0$
$r3 \% r2 = r1$
即存在k1, k2,使:
$r2 = r1 * k1$;
$r3 = r2 * k2 + r1 = r1 * (k1*k2+1)$
易知,k1与k1*k2 + 1 互质。所以r1是r2,r3的gcd。
算法正确性得证。