利用辗转相除法计算a和b最大公约数(greatest common divisor),该方法基于以下定理:
g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b)
设 a = kb + r,则有 r = a - kb.设d是a和b的一个公约数,则d也必是r的一个约数.r = a % b,所以d是b和 a % b 的一个公约数.由b的任意性,可得a和b的公约数都是b和 a % b 的公约数.又 a = kb + r,所以b和 a % b 的公约数都是a和b的公约数.所以 gcd(a, b) = gcd(b,