辗转相除求gcd的原理

题：求正整数m, n的最大公约数

解：
不妨设 m ＞ n，令 m % n = r。（r 为自然数）。

若 r = 0，则 n 即为所求，gcd(m,n) = n;

否则，有： r = m - kn（k 为正整数），则有：

可知： **gcd(m,n) = gcd(n,r)** 令 r₀ = n，r₁ = r，r_i+1 = r_i-1 % r_i（i 为正整数），则根据上式，有： gcd(n,r) = gcd(r₀,r₁) = gcd(r₁,r₂) = ... = gcd(r_i,r_i+1) = ... 上述等值变换，要么因为序列 { r_i } 递减至 1 而结束，要么因为 r_i 能被 r_i+1 整除 而提前终止。由于 1 可整除任何正整数，故最终总有： **gcd(m,n) = gcd(r_q,r_q+1) = r_q+1**