同余 学习笔记

前言:从寒假开始学了好几遍,都没完全掌握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 
    }
}

 

上一篇:青蛙的约会


下一篇:【模板】【数学】扩展欧几里得