在此写下我对于扩展欧几里得的见解，可能有错误，评论区指正，我看到就会改

裴蜀定理推论:a,b互质的充要条件是存在整数x,y使ax+by=1,那么由a,b互质，一定存在x,y,满足等式ax+by=1

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足等式： ax+by=gcd(a,b)

朴素欧几里得算法：gcd(a,b)=gcd(b,a
步骤：
ax1+by1=gcd(a,b)
bx2+(a%b)y2=gcd(a,b)
…
gcd(a,b)xn+0∗yn=gcd(a,b)
此时一定存在一组解xn=1,yn=0
然后需要以此回推，求出x1,y1 ax1+by1=bx2+(a%b)y2
a在计算机语言中可以表示为 a−a/b∗b
原式可化为
ax1+by1=ay2+b(x2−a/b∗y2)
x1=y2
y1=x2−a/b∗y2
得到了回推公式，递归求解即可 实现： void extend_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return; } else { extend_gcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; } } 注：方程有整数解(无穷多个)的充要条件是，a,b,互素，否则无整数解 如果让求解形如ax+by=gcd(a,b)∗p,同样也是有整数解的，因为这种式子可以转换为
a∗xp+b∗yp=gcd(a,b),此时得到的x和y，是原式的1p倍,乘p即可，但如果等号右边的系数不能整除gcd(a,b),则无解 定理：设a,b和m是整数,m>0,(a,m)=d,若d|b则ax≡b (mod m)恰有d个模m不同余的解,否则无整数解.（证明我也不会）
扩展欧几里得可以用于求解一元线性同余方程（形如ax≡b(mod m)）的解，可以建立以下方程ax+my=b，设d=gcd(a,m),如果d∤b则无整数解，否则，设a0=a/d , m0=m/d,求出a0∗x+m0∗y=1的解，然后乘上b/d,即为初始解x，共有d个模m剩余类满足方程