问题描述：
a 和 b的最大公约数是多少？
古代解法：辗转相除法
迭代过程：例如：
{a = 15 和 b = 12 }
=>{ a = 12,b = 15 - (15/12)* 12 = 3 }
=> {a = 3,b= 12 - (12/3)*3 = 0 }
=> { b = 0 所以a为最大公因数}
c++代码:
int gcd(int a,int b){return b?gcd(b,a%b):a;
}一行搞定。
实战： 对于平面坐标上的俩点 (x1,y1) 与(x2,y2) 他们之间的连线上有多少个点的坐标都是整数？（不包括给出的端点）
分析 ：我们初中就学过相似三角形,那么假如存在点p（x0，y0），那么 (y2-y1)/ (y0-y1) == (x2-x1)/(x0-x1)
变换一下形式 ： (y2-y1)/(x2-x1) ==(y0-y1) /(x0-x1) ， 这俩个分式的分子和分母都应该是整数，
那么假如左式不能约分，那么右式的分子分母应该等于左式地分子分母，
假如左式能约分 （假如约数有多个，即约完后又多种分式形式），那么右式的分子分母应该对应等于左式约分后对应的分子分母，所以约数的个数决定了解的个数。那么这题的解法就是 gcd( abs(x1-x2) , abs(y1-y2) ) -1
上述的问题与解答就是欧几里得原理。
下面我们再来看几个拓展的问题：
大家应该在高中学过二元一次不定方程对吧，那么对于 ax+by = c，的方程求整数解，
我们一般的解法都是找到一组特解，然后就很容易得到x = x0 + bt; y =y0 - at,其中t是整数 的这样的方程解
但是这样的效率是很低的，为什么呢？ 对于a b数字比较小的话，你可能花个几分钟能找出特解，但是当a和b是几千万甚至是超出了c++的最长整形数表示范围，那么你还打算暴力找特解吗？这样的时间花费是O（n）的。
所以我们从这个问题马上引出扩展欧几里得算法来求解二元一次方程：
对于ax+by = c ，我们认为约定好a>b哈（这个减少我们的讨论次数），那么由我们的欧几里得原理知道：
如果ax + by = c 有解，当且仅当gcd(a,b) 是 c 的倍数 为什么呢？
证明: https://blog.csdn.net/yoer77/article/details/69568676
如果 aa 和 bb 中有一个是 0，比如 a=0a=0，那么它们两个的最大公约数是 bb。这时裴蜀等式变成 by=mby=m，它有整数解 (x,y) 当且仅当 mm 是 bb 的倍数，而且有解时必然有无穷多个解，因为 xx 可以是任何整数。定理成立。
以下设 a和 b 都不为0。
设 A={
xa+yb;(x;y)∈Z2}A={xa+yb;(x;y)∈Z2} ，下面证明A中的最小正元素是 a 与 b 的最大公约数。
首先，A∩N?A∩N? 不是空集（至少包含|a||a| 和|b||b|），因此由于自然数集合是良序的， AA 中存在最小正元素d0=x0a+y0bd0=x0a+y0b。考虑AA中任意一个正元素p（=x1a+y1b）p（=x1a+y1b）对 d0d0 的带余除法：设p=qd0+rp=qd0+r，其中 qq为正整数，0≤r<d00≤r<d0。但是
r=p?qd0=x1a+y1b?q(x0a+y0b)∈Ar=p?qd0=x1a+y1b?q(x0a+y0b)∈A
而d0d0 已经是集合 AA 中最小的正元素了，又 0≤r<d00≤r<d0,所以 r=0r=0。
因此 d0 | pd0 | p。也就是说，A中任意一个正元素p都是 d0d0 的倍数，特别地：d0 | a、d0 | bd0 | a、d0 | b。因此 d0d0 是 aa 和 bb 的公约数。
另一方面，对 a 和 b 的任意正公约数dd，设 a=kd、b=lda=kd、b=ld，那么
d0=x0a+y0b=(x0k+y0l)dd0=x0a+y0b=(x0k+y0l)d
x0k+y0l≥1x0k+y0l≥1 ,因此 d | d0d | d0。所以 d0d0 是 aa 和 bb 的最大公约数。
在方程ax+by=max+by=m中，如果 m=m0d0m=m0d0，那么方程显然有无穷多个解： 
相反的，如果ax+by=max+by=m有整数解，那么 |m|∈A|m|∈A，于是由前可知 d0 | |m|d0 | |m|（即 d0 | md0 | m）。
m=1时，方程有解当且仅当a、b互质。方程有解时，解的集合是 
其中 (x0,y0)(x0,y0) 是方程ax+by=d的一个解，可由辗转相除法得到。
所有解中，有且仅有一个解(x,y) 满足 ?b≤x≤b，?a≤y≤a
下面我们来证明一下扩展欧几里得的递归过程：（先贴出代码）
int ex_gcd(int a,int b,int &x,int &y){if(b == 0){x = 1;y = 0;return a;}else{int r = ex_gcd(b,a%b,y,x);int t = y;y = x - (a/b)*y;x = t;return r;}
}我们给出递归的证明：
给定一个方程解 ：a * x1 + b * y1 = gcd(a,b) 由欧几里得原理=> b*x2 + (a%b)*y2 = gcd(b,a%b)
因为gcd(a,b) = gcd(b,a%b),所以，俩等式左侧相同，得到：
ax1+by1 = bx2 + ( a - (a/b) * b )*y2
=> ax1 + by1 = ay2 + b(x2 - a/b * y2) ......(对等原理)
=> x1 = y2 , y1 = x2 - a/b * y2 ,
那么递归的上层x1 y1 均依赖于 上层的a，b和下层的x2，y2，所以递归回溯得到的 x2 和 y2 可以求出当前层的 x1 y1
直到回溯结束。
那么递归的底层结束条件是什么呢？ 我们发现欧几里得原理的结束条件是b == 0 ，而扩展欧几里得 的x y系数是欧几里得原理的方法，所以递归到底层的时候一次能够会出现b==0 的情况 ，这个时候方程变为 ax = a 所以 此时解为 x = 1 ，y = 0
然后一直回溯，最后就能求出x y的解了