前言:从寒假开始学了好几遍,都没完全掌握QAQ
---------------
在讲同余之前,我们先来讲扩展欧几里得。
扩展欧几里得算法
首先,我们知道这样一个式子:
$gcd(a,b)=gcd(b,amodb)$。
辗转相除法,可以用来求两个数的最大公因数。
而扩展欧几里得($exgcd$),是用来求不定方程$ax+by=c$的解的。
裴蜀定理:设$a$和$b$不全为$0$,则存在$x$和$y$,使得$ax+by=gcd(a,b)$。
我们可以用数学归纳法证明。
在$gcd$的最后一步,当$b=0$时,$gcd(a,b)=a$。此时有一组解$x=1,y=0$。
当$b$不为$0$时,我们递归求$gcd(b,a%b)$。假设存在一对整数$x^{'},y^{'}$,满足
$bx^{'}+(a mod b)y^{'}=gcd(b,amodb)$。
因为$gcd(b,a mod b)=gcd(a,b)$,
所以$bx^{'}+(a mod b)y^{'}=gcd(a,b)$。
我们变换一下形式:$bx^{'}+(a-a/b*b)y^{'}=gcd(a,b)$,
移项得:$ay^{'}+b(x^{'}-a/by^{'}=gcd(a,b))$。
令$x=y{'},y=x^{'}-a/by^{'}$,我们就得到了$ax+by=gcd(a,b)$。
需要注意的是,通过$exgcd$找的解只是满足$ax+by=gcd(a,b)$的一组解,我们需要通过推导求得满足$ax+by=c$的解。
通过扩展欧几里得来推导同余方程的一组解
当$gcd(a,b)$整除$c$时,设$g=gcd(a,b)$,
现在有一组解$(x_{0},y_{0})$满足$ax_{0}+by_{0}=g$。
两边同时乘$c/g$,
则有$a(c/g*x_{0})+b(c/g*y_{0}=c)$,
对比原方程$a+by=c$,
我们可以得到:
$x=c/g*x_{0},y=c/g*y_{0}$。
当$gcd(a,b)$不整除$c$时,原不定方程无整数解。
通过同余方程的一组解推导同余方程的通解
对于两组满足同余方程的解:
$ax_{i}+by_{i}=c$
$ax_{j}+by_{j}=c$(假设$i$大于$j$)
通过联立移项得到:$a(x_{i}-x_{j})=b(y_{j}-y_{i})$
两边同除以$g(gcd(a,b))$,
得到$\frac {a}{g} (x_{i}-x{j})=\frac {b}{g} (y_{j}-y_{i})$
因为$\frac {a}{g}$和$\frac {b}{g}$是互质的,所以$\frac {b}{g}$是$x_{i}-x_{j}$的倍数,$\frac {a}{g}$是$y_{j}-y_{i}$的倍数($-\frac {a}{g}$是$y_{i}-y_{j}$的倍数)。
这样我们就知道了,$x$两个解的差值是$\frac {a}{g}$的倍数,$y$同理。
因此,
$x=x_{0}+\frac {b}{g}*k$
$y=y_{0}-\frac {a}{g}*k$
通过同余方程的通解推导同余方程的最小正整数解
通过$x=x_{0}+\frac {b}{g}*k$,
我们可以得到$xmod\frac {b}{g}=x_{0}$。
我们可以发现,当$x$为正整数时,通过上面的式子一定可以得出最小正整数解$x_{0}$
当求出的特解$x$小于$0$时,我们应该$while(x<0) x+=\frac {b}{g}$,让$x$大于$0$后,再进行操作。
对于$y$同理。
附扩展欧几里得模板代码:
void exgcd(int a,int b,int &x,int &y) {//通过裴蜀定理的证明我们可以知道,当前状态的解时通过下一状态的解求得的,exgcd求解 //本身就是一个自下而上递归的过程 int t; if (!b){x=1;y=0;} else{ exgcd(b,a%b,x,y); t=x; x=y;//当前状态的x是下一状态的y y=t-(a/b)*y;//求得这一阶段的y } }