方法一：辗转相除法 点击此处返回总目录
方法二：使用减法操作
方法三：使用位运算和减法操作
最大公约数（greatest common divisor）、最小公倍数（least common multiple）。
1. 求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
2. a,b的最大公约数gcd(a,b)与最小公倍数lcm(a,b)的关系是：
gcd(a,b) * lcm(a,b) = a*b
方法一、辗转相除法求最大公约数
【方法】
假设a>b，a除以b余数为c（c!=0）。则 a与b的最大公约数 = b与c的最大公约数。即：
gcd(a,b) = gcd(b,c)
比如要求6105和2146的最大公约数。求法如下：
6105＝2146×2＋1813 6105与2146的最大公约数等于2146与1813的最大公约数 2146＝1813×1＋333 2146与1813的最大公约数等于1813与333的最大公约数 1813＝333×5＋148 1813与333的最大公约数等于333与148的最大公约数 333＝148×2＋37 333月148的最大公约数等于148与37的最大公约数 148＝37×4＋0 148月37的最大公约数为37。（除尽）。 因此37为8251与6105的最大公因数。
【证明】
我简单的证明一下：
若要求a、b的公约数，不妨设a>b。
假设a = kb+c。即a除以b的余数是c。
1. 如果r是a和b的公约数，则r也是c的约数。
证明：因为r是a和b的公约数，所以a%r=0，b%r=0。而a%r = (kb+c)%r = c%r = 0。所以r也是c的约数。r是c和b的公约数。
2. 如果t是b和c的公约数，则t也是a的约数。
证明：因为t是b和c的约数，所以b%t=0, c%t = 0。而a%r = (kb+c)%r = 0。所以，t也是a的约数。t是a和b的公约数。
由1和2得，a和b的公约数也是b和c的公约数，b和c的公约数也是a和b的公约数。因此，a和b的公约数与b和c的公约数是相同的。当然最大公约数也是相同的。所以gcd(a,b) = gcd(b, a%b)
【网上更详细的证明】
我把网上的更详细的证明放在下面，有兴趣的可以看一下。没兴趣的就算了，记住方法就行。
【代码】
结果：
方法二、使用减法代替取余操作
方法一中使用了取余操作。对于大整数而言，取余运算(其中用到除法)是非常昂贵的开销，将成为整个算法的瓶颈。
我们可以用减法操作来代替取余操作。
【方法】
假设a>b，a-b=c（c!=0）。则 a与b的最大公约数 = b与c的最大公约数。即：
gcd(a,b) = gcd(a-b,b)
比如要求6105和2146的最大公约数。
6105-2146 = 3959 6105与2146的最大公约数等于3959与2146的最大公约数
3959-2146 = 1813 3959与2146的最大公约数等于2146与1813的最大公约数
2146-1813 = 333 2146与1813的最大公约数等于1813与333的最大公约数
1813-333 = 1480 1813与333的最大公约数等于1480与333的最大公约数
1480-333 = 1147 1480与333的最大公约数等于1147与333的最大公约数
1147-333 = 814 1147与333的最大公约数等于814与333的最大公约数
814-333 = 481 814与333的最大公约数等于481与333的最大公约数
481-333 = 148 481与333的最大公约数等于333与148的最大公约数
333-148 = 185 333与148的最大公约数等于185与148的最大公约数
185-148 = 37 185与148的最大公约数等于148与37的最大公约数
148-37 = 111 148与37的最大公约数等于111与37的最大公约数
111-37 = 74 111与37的最大公约数等于74与37的最大公约数
74-37 = 37 74与37的最大公约数等于37与37的最大公约数
37-37=0 37与37的最大公约数等于37。
【证明】
若要求a、b的公约数，不妨设a>b。
1. 如果r是a和b的公约数，则r也是a-b的约数。
证明：因为r是a和b的公约数，所以a%r=0，b%r=0。而(a-b)%r = 0。所以r也是a-b的约数。r是a-b和b的公约数。
2. 如果t是a-b和b的公约数，则t也是a的约数。
证明：因为t是a-b和b的约数，所以(a-b)%t=0, b%t = 0。而a%r = (a-b+b)%r = 0。所以，t也是a的约数。t是a和b的公约数。
由1和2得，a和b的公约数也是a-b和b的公约数，a-b和b的公约数也是a和b的公约数。因此，a和b的公约数与a-b和b的公约数是相同的。当然最大公约数也是相同的。所以gcd(a,b) = gcd(a-b, b)
【代码】
结果：
【分析】
虽然不再需要进行大整数的取余运算，转变成了简单的减法运算。但是同样有不足之处，就是迭代的太慢了。如果遇到(100000000,1)这类情况，就相当让人郁闷了。
方法三、使用位运算和减法来求解
【原理】
我们使用下列两个公约数的性质进行分析：
1. 对于a和b，如果a = kx, b = ky , 则 gcd(a,b) = k* gcd(x, y)
比如12 = 2*6 ， 18 = 2* 9 ， 那么12和18的公约数 = 2*( 6和9的最大公约数)
2. 对于a和b，如果p是素数、p是a的约数并且p不是b的约数，则gcd(a, b) = gcd(a/p, b)
p是a的约数但是不是b的约数，说明p可以拿掉。比如3是12的约数，但是3不是16的约数，所以gcd(12,16)等于gcd(4,16)。为什么要抢到p是素数呢？因为如果是合数，就不对了。比如6是12的约数，6不是16的约数，但是gcd(12,16)不等于gcd(2,16)。
【方法】
根据上面两个性质，我们就可以有以下方法：
若a、b都为偶数，则gcd(a,b) = 2 * gcd(a/2, b/2) //利用性质1。把2提出来。
若a为偶数，b为奇数，则gcd(a,b) = gcd(a/2, b) //利用性质2。2为素数。
若b为偶数，a为奇数，则gcd(a,b) = gcd(a, b/2) //性质2。
若a、b都为奇数，则gcd(a,b) = gcd(a-b, b) //方法二的减法操作。
【代码】
结果：
方法一，快不好。方法二好不快。方法三，又快又好。
