一、辗转相除法定义
辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数（Greatest CommonDivisor：gcd）。否则就用余数来除刚才的除数；
再用这新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。即：gcd（x,y）表示x与y的
最大公约数，有gcd(x,y)=gcd（y,x%y），如此便可把原问题转化为求两个更小数的公约数，直到其中一个数为0，剩下的另外一个数就是两者的最
大公约数。 - 例如：求 4453 和 5767 的最大公约数时，可作如下除法．
5767÷4453＝1 余 1314
4453÷1314＝3 余 511
1314÷511 ＝2 余 292
511 ÷292 ＝1 余 219
292 ÷219 ＝1 余 73
219÷73＝3 于是得知，5767 和 4453 的最大公约数是 73。辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数。
二、欧几里得辗转相除法证明
辗转相除法就是给出了一个关系：gcd（a,b）=gcd(b,r)gcd（a,b）=gcd(b,r)，其中a、b、r满足a=bq+r。
设u同时整除a和b，则有
a=su,b=tua=su,b=tu
则r=a−bq=su−tuq=(s−tq)ur=a−bq=su−tuq=(s−tq)u，得到u也整除r。反过来，每一个整除b和r的整数vv，则有
b=s′v，r=t′v.b=s′v，r=t′v.
则a=bq+r=s′vq+t′v=(s′q+t′)va=bq+r=s′vq+t′v=(s′q+t′)v，得到v也整除a。
综上：a和b的每一个公因子也是b和r的一个因子，反之亦然。所以a和b的全体公因子集合就与b和r的全体公因子集合相同。所以gcd（a,b）=gcd(b,r)。 三、推论
推论一：如果d=gcd(a,b)d=gcd(a,b)，则能找到正的或负的整数kk和ll，使得d=ka+lb.d=ka+lb.
我们在使用辗转相除法时，由于gcd(a,0)=agcd(a,0)=a,我们可以假设b≠0b≠0。这样我们能写出如下
a=bq1+r1(0<r1<b)a=bq1+r1(0<r1<b)公式一
b=r1q2+r2(0<r2<r1)b=r1q2+r2(0<r2<r1)
r1=r2q3+r3(0<r3<r2)r1=r2q3+r3(0<r3<r2)
r2=r3q4+r4(0<r4<r3)r2=r3q4+r4(0<r4<r3)
……..
只要余数r1,r2,r3,r4.....r1,r2,r3,r4.....不是0就继续写下去。从右边的不等式，可以看出余数形成了一个严格递减序列：b>r1>r2>r3>....>0b>r1>r2>r3>....>0。因此最多b步，0这个余数必然出现。
rn−2=rn−1qn+rnrn−2=rn−1qn+rn
rn−1=rnqn+1+0rn−1=rnqn+1+0
此时，我们就得到rn=gcd(a,b)rn=gcd(a,b);
在公式一中，我们可以推出r1=a−q1br1=a−q1b,所以r1r1可以写成k1a+l1bk1a+l1b的形式。所以
r2=b−q2r1=b−q2(k1a+l1b)=(−q2k1)a+(1−q2l1)b=k2a+l2br2=b−q2r1=b−q2(k1a+l1b)=(−q2k1)a+(1−q2l1)b=k2a+l2b，显然，通过这一串余数r3,r4.....r3,r4.....的结果，推导出rn=gcd(a,b)=ka+lbrn=gcd(a,b)=ka+lb。
推论二：如果一个素数p整除乘积ab，则p必整除a或b。
因为p整除ab，所以ab=prab=pr。
因素数p仅有因子p和1，所以如果p不整除a，则gcd（a，p）=1，根据上面的推论一我们能找到整数kk和ll，使得1=ka+lp1=ka+lp.在等式两边同时乘以b，我们得到：b=kab+lpb=kpr+lpb=p(kr+lb)b=kab+lpb=kpr+lpb=p(kr+lb)，到此显然p整除b。
同理，当p不整除b时，可以证得p整除a。
综上，命题“如果一个素数p整除乘积ab，则p必整除a或b”得证。
注意：不妨举几个例子印证推论二。
- 13是2652的一个因子，以及2652=6*442，就可以得出13是442的因子。
- 6是240的一个因子，而240=15*16，但6既不是15也不是16的因子。why？这表明p是素数这个前提是不可或缺的。
以上内容来自https://blog.csdn.net/so_geili/article/details/54970799#t0
四、辗转相除法递归函数
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b)
} 这个算法称为欧几里得算法。既然是是递归，那会栈溢出吗？答案是不会。可以证明，gcd函数递归层数不超过
利用gcd还可以求出两个整数a和b的最小公倍数 lcm(a,b) 。这个结论很容易由唯一分解定理得到 gcd(a,b)*lcm(a,b)=a*b.
不过记得函数实现的时候应该写成 a/gcd(a,b)*b。这样一来可以防止溢出！
京公网安备 11010502036488号