拓展欧几里德算法的求解证明及基本应用

拓展欧几里德要解决的问题就是给定方程$ax+by==gcd(a,b)$，已知$a，b$，求解$x，y$且使$|x|+|y|最小$，而且既然是欧几里德，顺便也能把$gcd(a,b)$求出来
因此，拓展欧几里德也就可以解$ax+by==c$这种方程了，虽然右边不是$gcd(a,b)$但我们只要将得到的解乘以$\frac{c}{gcd(a,b)}$即可
下面讲一下拓展欧几里德算法的证明

首先已知$a{x}_1+b{y}_1==gcd(a,b)$，如果把$a$换成$b$，$b$换成$a\%b$，那么这个方程也还是成立的，也就是$b{x}_2+(a\%b)y_2==gcd(b,a\%b)$，然后我们由欧几里德可以知道$gcd(a,b)==gcd(b,a\%b)$，那么上面的式子对应一下，就能得到$a{x}_1+b{y}_1==b{x}_2+(a\%b)y_2$，然后$a\%b$又可以化成$a-\lfloor (\frac{a}{b})\rfloor b$，那么就可以得到$a{x}_1+b{y}_1==b{x}_2+(a-\lfloor (\frac{a}{b})\rfloor b)y_2$，右边化简一下，把$a{y}_2$提到前面就是$a{x}_1+b{y}_1==a{y}_2+b(x_2-\lfloor \frac{a}{b})\rfloor y_2)$，这样对应一下，$x_1=y_2，y_1=x_2-\lfloor (\frac{a}{b})\rfloor y_2$，最后我们还要注意到递归的边界条件，当$b=0$时，$gcd(a,b)=a$，所以此时$x=1,y=0$
所以就可以来写代码了

ll exgcd(ll a,ll b,ll &x,ll &y){
   
	if(b==0){
   
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
}

一旦理解了算法，写起来就比较容易了

逆元，逆元其实就是在一个代数系统下类似与倒数的定义，我们在这里定义的就是模n下的逆元，比如$ab\equiv 1(\%n)$，如果不考虑这个同模的话，$a/b$就是$b/a$的倒数(逆元)，现在有了模n的情况，就不叫倒数，叫逆元了
所以求逆元一般就是指已知$ab\equiv 1(\%n)$，给定$a/b$，求$b/a$，然后还有一个限制就是只有$a/b$和$n$互质时，才有对应的逆元
现在假设有$ax\equiv 1(\%n)$，给定$a$，求$a$的逆元$x$，因为刚才说$a$要和n互质时才有逆元，所以$gcd(a,n)\equiv 1$，所以有$ax+ny\equiv 1$，所以我们用拓展欧几里德求出$x$即可，当然如果顺便得到的gcd值不为1，也就是两数不互质的话，就不存在逆元，返回-1

ll inv(ll a,ll m){
   
	ll x,y;
	ll d=exgcd(a,m,x,y);
	if(d==1){
   
		//x可能是负数
		return (x%m+m)%m;
	}
	return -1;
}

拓展欧几里德还能用来解形如$ax+by==c$的方程，其中有解的条件是$gcd(a,b)|c$，所以其实方法就是先通过拓展欧几里德解出方程$a{x}^{\prime }+b{y}^{\prime }==gcd(a,b)$，然后$x=\frac{x^{\prime }c}{gcd(a,b)}，y=\frac{y^{\prime }c}{gcd(a,b)}$，这得到的就是方程的一个特解，而通解就是$x_0=x\pm \frac{kb}{gcd(a,b)}，y_0=y\mp \frac{ka}{gcd(a,b)}$，其中$k$为任意整数，这个证明怎么得来的呢，有个比较简单的理解，我们现在已知$ax+by==c$的一个特解$x，y$，那么通解代入的形式肯定是$a(x+??{?}_1)+b(y+??{?}_2)==c$，对比一下可以得出$a??{?}_1+b??{?}_2==0$，那显然就是用$gcd(a,b)$做分母，分子包含另一个的k倍即可，然后符号相反，就比如$a\frac{kb}{gcd(a,b)}$和$b\frac{-ka}{gcd(a,b)}$，这样凑齐来就是0了，因此这就是通解
然后很多情况下我们要求的是最小整数解，而且有时候有负数来捣乱，所以应该是$x=(x\%abs(\frac{b}{d})+abs(\frac{b}{d}))\%abs(\frac{b}{d})$