本文整理梳理了一些有关扩欧算法的内容，力求深入浅出便于理解，对一些作者在初次接触此算法时的不解（比如一些不是很好看出来的“易得”“显然”hh）通过数学形式呈现与推导。本文涉及的数学推导非常简单。代码均采用C++。
限于作者能力有限可能有些地方表述不清，请读者多多包含！
【预备知识】
1.基础数论概念（整除、质数合数、gcd/lcm…或者说你已经懂了辗转相除法是怎么用）
2.递归、子函数
就让我们从原本的欧几里得算法开始。
【欧几里得算法】（EUCLID 即辗转相除法）
//a,b均为任意非负整数且不同时为零
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
通过此可以求出a,b的最大公约数。
【扩展欧几里得算法】
就是欧几里得算法的推广，用于计算满足d=gcd(a,b)=ax+by的整系数x和y。
贝祖定理
若a,b是整数，设d=gcd(a,b)， 那么对于任意的整数x、y, d|ax+by, (p|q 表示p整除q)
特别地，一定存在整数x,y，使ax+by=d成立。
【应用1】求一元二次线性方程的整数解（ax+by=c）
[ 思路 ]
1.求出满足a*x0+b*y0=gcd(a,b)的特殊解（x0,y0）.
2.方程两边同时乘c/gcd(a,b)，(等式的性质) 即 将x0、y0乘c/gcd(a,b)就得到了原方程ax+by=c的通解.
P.S
1）c/gcd(a,b)可能不是整数， 这时候说明原方程没有整数解(即x和y不全为整数)
2）满足原方程的解有无数个，一般题目会要求求有特殊性质的解。 例如大于10的最小整数解（x,y）诸如此类……
接下来是推导实现过程。
for1
1）根据GCD递归定理，对于任意非负整数a和任意正整数b，
gcd(a,b)=gcd(b,a%b) <1>
(详细证明见算法导论P547)
根据贝祖定理，
a*x0+b*y0=gcd(a,b) <2>
b*x1+(a%b)*y1=gcd(b,a%b) <3>
所以， a*x0+b*y0=b*x1+(a%b)*y1
又因， a%b=a-[a/b]*b （[]表示向下取整）
故有， a*x0+b*y0=b*x1+(a-[a/b]*b)*y1
解得，
x0=y1,y0=x1-[a/b]*y1
（我也不知道怎么解的…带回去是成立的…欢迎探讨）
2）g(a,b)递归到最后其实是（d,0） 所以，d*xn+0*y0=gcd(d,0)=d;
故,一个解一定为（1，0）(xn=1,yn=0) (不是x0,y0) 然后往上递归回溯即可
[代码for1]
void exgcd(ll a,ll b,ll& x,ll& y)//LL==long long
{
if(b==0) {x=1;y=0;}
else
{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
//注意x,y位置的交换 巧妙地表示了上述x0,y0
}
}
Q1:why x、y是&x、&y?
for2
已知特解x0、y0,设(右边gcd的那个的)通解为x’、y’
a*x0+b*y0=gcd(a,b) 即 a*x0-[b*(-y0)]=gcd(a,b) <1>
由于被减数、减数同时加上一个相同的数，差不变，
我们选择加上a,b的最小公倍数[a,b]=a*b*gcd(a,b)，或者它的倍数（*k）
[a*x0+a*b*gcd(a,b)]-[b*(-y0)+(-a*b*gcd(a,b))]=gcd(a,b)
a*(x0+b*gcd(a,b))-b*[(-y0)+(-a*gcd(a,b))]=gcd(a,b)
又因
ax’+by’=gcd(a,b) <2>
解得，
x’=x0+b/gcd(a,b)*k (k为任意整数)
y’=y0-a/(gcd(a,b)*k
乘c/gcd(a,b)
X=x0*c/gcd(a,b)+k*b/(gcd(a,b)
Y=y0*c/gcd(a,b)-k*a/gcd(a,b)
注意，如果右边加数也扩大的话会导致漏解
因为c>=gcd,所以在原来解的基础上都乘c/gcd会导致周期放大为原来c/gcd,
也就是说x,y属于[b*c/gcd^2，a*c/gcd^2],所以导致漏解。
Q2：?漏解？
[反思·运行时间]
EXTENDED-EUCLID（扩欧）与EUCLID所执行的递归调用次数相等，因此，它们的运行时间相同，两者相差不超过一个常数因子，即对于a>b>0，递归调用的次数为O（lg b）
【应用2】求解线性同余方程
ax=c(mod p)等价于ax%p=c%p,直接转化为一元二次方程问题求ax+py=c的解
【应用3】求解乘法逆元
ax=1(mod p)
一般把x的最小非负整数解作为a的乘法逆元
也是转化为一元二次方程ax+py=1的解。
部分资料来源网络和算法导论。还没写完的应用2、3之后编辑。
感谢
(91条消息) 扩展欧几里得算法(简单易懂，详细分析)_鲜果维他命的博客-CSDN博客_拓展欧几里得算法
一些关于数论的基本证明可以看算法导论31章节数论篇
（作者也比较推荐数学的小蓝书 初中卷即可 很好理解与入门qwq）
ALL IN ALL，欢迎指正与探讨。