设 a 和 b 的最大公约数为 c ； 则有 c = gcd( a , b ) ; 设 a = x * c , b = y * c , 其中 x 与 y 互质 （因为 c 是最大公约数） 设 g = a%b = a - i * b = (x - i * y )... 本文是参考新浪博客而写。 欧几里得算法 , 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式 gcd(a, b) = gcd(b, a mod b) 其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b