Q1.为什么是 gcd(b,a % b) 而不是gcd(a % b , b)

可以看得很清楚了gcd(b,a % b)可以保证：在大小顺序不符的时候 可以调换顺序；保留下较小值,用较大值去模较小值从而得到一个比较小值更小的值，而gcd(a%b,b) 最多只能工作一次

• 如果gcd(a , b) = g , a = m*g , b = n*g 则有：m 和 n一定互素(互素是指m和n的最大公约数为1, 并不是说m , n都为素数)。原因是如果 m，n不互素的话 就可以提取m , n的公约数 乘到g上，这与g为最大公约数相矛盾

• a和b的最大公约数是两数共有的素因数的乘积。

例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17；最大公约数就等于 3 x 7 = 21 ; 那为什么不用分解质因数的方法呢，因为分解质因数要麻烦得多，尤其是当数很大的时候，很多加密算法之所以很难破解的原因就是分解质因数难；而辗转相除法的优点就是可以不必计算出所有质因数（有的地方叫素因数）的前提下求出最大公约数。这个性质其实很好得出，就拿上边的例子来说，g = 3x7 已经满足了倍数关系呢，但是不是最大的呢，当然是最大的，想要增大g  对于462来说可以乘以2 ，g = 2 x 3 x 7，现在用1071除以g得到 3 x 7 x 17 / 2 , 因为它们都是素数除了自己和1 其它的都不能整除的，你可能又有疑问了 3，7，17都不能被2整除，这没错，那它们的乘积呢，再看如下性质 ：如果一个数w互素于数列a1、a2、…、an 中的每一个数，则w也一定互素于它们的乘积a1 × a2 × … × an，2 和 3，7，17 都是互素的，乘积也是互素，当然不能整除啦，这个性质我不会证明，所以打住吧。

• 用辗转相除法计算两个数的最大公约数所需的步数不会超过其中较小数的位数h的5倍

• 两个整数的最大公约数等于其中较小的数和两数的差的最大公约数

gcd(a ,b) = gcd(abs(a - b) , min(a,b))

Q2.为什么不用这种方式求最大公约数？

当a b的差值很小时你会发现它也非常快，但是gcd(b , a%b) 更快

Q3.从 gcd(a ,b) = gcd(abs(a - b) , min(a,b)) 到 gcd(b , a%b)

假设 a >= b （在Q1 已经说明了我们总可以调换大小顺序的 保证左大右小）则
a = k*b + r (k = 1,2,3,...)这个应该很好想到(k 为商，r为余数)
gcd(abs(a - b) , min(a,b))的目的就是不断地用较大值减去较小值，一直减到不够减，即a=r的时候，与其不断地减减减 何不直接取余？！

Q4.a b c的最大公约数怎么算呢？

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).

• 两数的最大公约数可以用两数的整数倍相加来表示，这个重要的等式叫做贝祖等式

写成一般的形式： gcd（a , b） = a*x + b*y  为了方便令gcd(a,b) = D

a*x + b*y = D；（1）

因为 gcd(a,b) = gcd(b, a % b) 辗转相除一次之后则有

b*(x ’ ) + (a % b)*(y ' ) = D---> b*(x ' ) + (a - a/b * b)*(y ' ) = D

再进一步整理为：a*（y ‘） + b*( (x ’ ) - a/b*(y ' ))= D  （2）

根据（1）（2） 可以得到 x = (y ' ) ; y = (x ’ ) - a/b*(y ' )

当b = 0时，a*x = gcd(a,0) = a, 得 x = 1. 这样我们就可以通过辗转相除求得x ，y的值，这就是扩展欧几里德 ，模板如下：