欧几里得算法的[相关]

欧几里得算法原理与应用

定理 ：任意两个整数之间的最大公约数，其数值等同于这两个整数中较小者与较大者除以较小者后所得余数的最大公约数。最大公约数（greatest common divisor）通常用gcd表示。

证明 ：
设a除以b等于k余r，即a = bk + r。由此可得，需验证gcd(a, b) = gcd(b, r)。
1. 假设c为a与b的最大公约数，那么可以表示为a = mc、b = nc，其中m和n互为质数，否则c将无法成为最大公约数。m和n均为整数。
2. 余数r可表示为r = a - bk = (m - kn)c，因此c也是r的一个因数。
3. 接下来需要证明c是b与r的最大公约数，即要证明(m - kn)与n互素。若(m - kn)与n不互素，则存在一个大于1的整数d使得m - kn = xd、n = yd。由此推得m = xd + kyd = (x + ky)d，则有gcd(m, n) = d，这显然与m和n互素的条件相矛盾。因此假设不成立，说明(m - kn)与n确实互素 ——》由此得出c即为gcd(b, r)，从而证得gcd(a, b) = gcd(b, r)。证毕。

举例 ：
计算gcd(26, 8)，可转化为计算gcd(8, 26-3×8)=gcd(8, 2)=2；再如计