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

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

首先已知 $ax_1+by_1==gcd(a,b)$ ，如果把 $a$ 换成 $b$ ， $b$ 换成 $a\%b$ ，那么这个方程也还是成立的，也就是 $bx_2+(a\%b)y_2==gcd(b,a\%b)$ ，然后我们由欧几里德可以知道 $gcd(a,b)==gcd(b,a\%b)$ ，那么上面的式子对应一下，就能得到 $ax_1+by_1==bx_2+(a\%b)y_2$ ，然后 $a\%b$ 又可以化成 $a-\lfloor (\frac{a}{b})\rfloor b$ ，那么就可以得到 $ax_1+by_1==bx_2+(a-\lfloor (\frac{a}{b})\rfloor b)y_2$ ，右边化简一下，把 $ay_2$ 提到前面就是 $ax_1+by_1==ay_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$ 时， $g c d (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下的逆元，比如 $\equiv1(\%n)$ ，如果不考虑这个同模的话， $a / b$ 就是 $b / a$ 的倒数(逆元)，现在有了模n的情况，就不叫倒数，叫逆元了
所以求逆元一般就是指已知 $ab\equiv1(\%n)$ ，给定 $a / b$ ，求 $b / a$ ，然后还有一个限制就是只有 $a / b$ 和 $n$ 互质时，才有对应的逆元
现在假设有 $ax\equiv1(\%n)$ ，给定 $a$ ，求 $a$ 的逆元 $x$ ，因为刚才说 $a$ 要和n互质时才有逆元，所以 $gcd(a,n)\equiv1$ ，所以有 $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;
}

拓展欧几里德还能用来解形如 $a x + b y = = c$ 的方程，其中有解的条件是 $g c d (a, b) ∣ c$ ，所以其实方法就是先通过拓展欧几里德解出方程 $a x^{'} + b y^{'} = = g c d (a, b)$ ，然后 $x=\frac{x'c}{gcd(a,b)}，y=\frac{y'c}{gcd(a,b)}$ ，这得到的就是方程的一个特解，而通解就是 $x_0=x\pm \frac{kb}{gcd(a,b)}，y_0=y\mp\frac{ka}{gcd(a,b)}$ ，其中 $k$ 为任意整数，这个证明怎么得来的呢，有个比较简单的理解，我们现在已知 $a x + b y = = c$ 的一个特解 $x ， y$ ，那么通解代入的形式肯定是 $a(x+???_1)+b(y+???_2)==c$ ，对比一下可以得出 $a???_1+b???_2==0$ ，那显然就是用 $g c d (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})$