裴蜀定理
裴蜀定理：对于任意整数a、b，存在整数x、y，使得 $ax + by = (a, b)$。特别地，如果$(a,b)|c$，那么$ax+by=c$有整数解。裴蜀定理表明，如果a和b互质，那么$ax+by=1$有整数解。
证明
证明：$ax+by=c$有整数解的充要条件是$(a,b)|c$
充分性证明
这里要证明的是，$ax+by=c$，如果$(a,b)|c$，那么这个方程有整数解。
1、定义集合$S={ax+by|x,y\in Z}$，显然$S$包含了所有的$a$和$b$的线性组合。
2、我们假设$a,b >0$，至于负号，可以扔到$x,y$里。可以想到，$a$和$b$都一定是$S$的元素。
3、考虑$S$中的最小正整数$d$，那么$d$一定是$a$和$b$的线性组合，即$d=ax_0+by_0$。
4、考虑到使用带余除法的形式表示$a=qd+r$，其中$0\leq r < d$。那么$a=qd+r=q(ax_0+by_0)+r$。也就是$r=a-q(ax_0+by_0)=a(1-qx_0)+b(-qy_0)$。所以$r$也是$a$和$b$的线性组合。也就是$r\in S$。
5、但是$r < d$，与$d$是$S$中的最小正整数矛盾。所以，$r$的取值必须是$0$。
6、所以我们能够得到：$d|a,d|b$，也就是说$d$是$a$和$b$的公约数，也就是$d|(a,b)$。
7、根据欧几里得算法（辗转相减的部分）我们得知，$(a,b)$也是$a$和$b$的一个线性组合，所以$(a,b)\in S$。
8、考虑$d$和$(a,b)$的关系。可以想到从$(a,b)$出发，加/减若干个$a$或者$b$，可以得到$S$中的所有元素。而且$(a,b)|a,(a,b)|b$，所以加/减的若干个$a$或者$b$都是$(a,b)$的倍数，所以可以得到$\forall (a,b)|x,st. x\in S$。
9、所以$d$也是$(a,b)$的倍数，显然$d=(a,b)$
所以，我们知道，$ax+by=(a,b)$有整数解。同时，上述过程也说明了，$ax+by=c$，如果$c|(a,b)$并且$c < (a,b)$，那么$ax+by=c$没有整数解。
如果$(a,b)|c$，设$c=(a,b)k$，那么，已知$ax\equiv (a,b)(\mod b)$有整数解，也就是说$kax\equiv k(a,b)(\mod b)$也是有整数解的，也就是说$ax+by=c$有整数解。
必要性证明
这里要证明的是，$ax+by=c$如果有整数解，那么必须满足$(a,b)|c$。
根据之前的推导可知，$(a,b)$的所有倍数都在集合$S$中，也就是说，$ax+by=c$如果有整数解，那么$c$一定是$(a,b)$的倍数，即$(a,b)|c$。
证毕。
上述证明说明了，$ax+by=c$有整数解的充要条件是$(a,b)|c$。也给出了这种方程的一种求法，也就是先求解$ax+by=(a,b)$这个方程，再把$x,y$乘上$\frac{c}{(a,b)}$即可。
另一个角度
首先证明，当$(a,b)=1$时，$ax+by=1$有整数解。
其实，我们知道，$ax+by=1$可以转换成$ax\equiv 1(\mod b)$，根据欧拉定理可知，当$(a,b)=1$时，$ax\equiv 1(\mod b)$有整数解$x\equiv a^{φ(b)-1}(\mod b)$。
有了这个结论之后，我们也知道$ax+by=gcd(a,b)$可以转换成$\frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=1$来求解。所以，$ax+by=gcd(a,b)$有整数解。
至于$ax+by=c$，其中$(a,b)|c$，我们可知，$ax\equiv c(\mod b)$可以转换为$x\equiv a^{-1}c(\mod b)$也就是$x\equiv a^{\phi(b)-1}c(\mod b)$。所以，$ax+by=c$有整数解。
可以发现，欧拉定理和裴蜀定理联系在了一起。
扩展欧几里得算法(exgcd)
exgcd主要是用于求解$ax+by=(a,b)$的整数解。
考虑到求$gcd$的过程。假设$a>b$，我们递归求$gcd$基于一个基本的公式：
考虑两组解：
可以得到：
我们知道$a\%b=a-\lfloor\frac{a}{b}\rfloor \times b$
所以：
显然可见，$x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$。
总结一下，上面公式说的是：
结合递归求$gcd$的过程：
int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}可以写出$exgcd$的代码为：
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);//先去递归求解x2和y2的值
int t=x;//t存一下x2的值
x=y;//x1=y2
y=t-a/b*y;//y1=x2-a/b*y2
return d;
}可以想到，当$b=0$时，$ax+by=1$也就是$ax=1$，所以$x=1,y=0$，这样，我们就得到了一组解（解有无穷多个）。
上面的代码可以简化一下：
ll exgcd(ll a,ll b,ll& x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}解与通解
假设$(x_0,y_0)$是$ax+by=(a,b)$一组解，假设$k=\frac{c}{(a,b)}$，可知$(kx_0,ky_0)$是$ax+by=c$的一组解。也就是：
假设$(x_1,y_1)$是$ax+by=c$的另外一组解，那么：
所以：
可知$(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$,所以：
$t$为任意整数。可以观察到，$x$的解和$y$的解增长性相反（必然，因为两者的和固定，一个增加，另一个必然减少），所以，我们可以得到$ax+by=c$的通解为：
这里也可以转换成同余式的形式：
应用
1、求逆元
求$a$模$p$的逆元，其实就是求解方程$ax\equiv 1(\mod p)$。
转换成不定方程：$ax+py=1$，然后使用$exgcd$求解即可。最后$x$就是$a$模$p$的逆元。
参考代码求解$a$模$b$的逆元：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
ll exgcd(ll a,ll b,ll& x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}
int main(){
cin>>a>>b;
ll x,y;
exgcd(a,b,x,y);
x=(x%b+b)%b;
cout<<x;
return 0;
}2、极值和解的数量
思考对于方程$ax+by=c$并且$(a,b)|c$，$x$和$y$的正整数解（$x$和$y$均为正整数）的数量，以及正整数解中$x$和$y$的最大值、最小值。回顾之前总结的通解的形式：
以及：
根据同余式可得，正整数解数量为
3、【青蛙的约会】
本题所求的式子为：
将同余方程转换成不定方程：
两个未知数$(t,s)$，可知$t$的最小非负整数解即为所求。
4、【Gift Dilemma】
给定$A,B,C,P$，求$Ax+By+Cz=P$有多少个非负整数解，也就是$x,y,z$都要大于等于零。
三个未知数的不定方程的求解就难以使用$exgcd$来直接求解了。我们要把问题转换成我们已经求解过的问题。也就是：
可以想到，$z$的取值范围是$0\leq z\leq \lfloor \frac{P}{C} \rfloor$。根据题目的数据范围可知，$\frac{P}{C}$并不会很大，最多到$5\times 10^5$，所以我们可以枚举$z$的取值，从而得到很多个二元一次不定方程，这样就可以进行求解了。
发表评论