辗转相除求gcd的原理

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

不妨设 m>n, gcd(m,n) = x, 令 m%n = r. 则 m = ax, n = bx(a,b 均为正整数).

若 r = 0, 则 n 即为所求;

否则, 有

r = m - kn
= (a - bk)x(k为正整数)

可知:

gcd(m,n) = gcd(n,r)

令 r0 = r, r(i+1) = n%ri,则根据上式,有:

gcd(n,r0) = gcd(r0,r1) = ... = gcd(ri,r(i+1)) = r(i+1)