扩展欧几里德定理
对于与不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么存在唯一的整 数 x，y 使得 gcd（a，b）=ax+by。
扩展欧几里德原理”是由“欧几里德原理”扩展来的（PS：废话），有的书上叫“费蜀（Bezout）定理”，总之有个这个事
c=gcd(a,b)表示a，b两数的最大公约数，则存在：ax+by=c一定存在整数x，y使等式成立
先说一下“欧几里德原理”，其实就是“辗转相除法”，也就是中国老祖先的“更相减损之术”，这个算法的主要目的是求出两个数的最大公约数，具体是一个递归的过程，简单说来是：
gcd（a,b）=gcd(b,a mod b)
终止条件是：gcd（a,b）中的a mod b=0，然后输出b
求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以 结束。