我们接着上面的欧几里得算法说
扩展欧几里得算法
扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足贝祖等式\(^①\): ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。
①:裴蜀定理:
裴蜀定理\((Bezouts identity)\)是代数几何中一个定理,其内容是若设a,b是整数,则存在整数x,y,使得ax+by=gcd(a,b),(a,b)代表最大公因数,则设a,b是不全为零的整数,则存在整数x,y,使得ax+by=(a,b),这里我们不做过多讨论(其实Base-2部分就有记录)。
附上美照:
“对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然
存在整数对 x,y ,使得 gcd(a,b)=ax+by。”我们可以这么描述扩展欧几里得算法
证明
\(gcd(a,b)=gcd(b,a\text %b),\)
令\(ax+by=gcd(a,b)=gcd(b,a \space mod\space b)=c,\)
而
\]
又因为\((a\space mod\space b)=a-\lfloor\frac ab\rfloor b\)
得$$bx'+ay'-\lfloor\frac ab\rfloor by'=ax+by$$
于是我们可以得到递归过程中层与层之间传递的式子:
\]
int exgcd(int &x,int &y,int a,int b){
if (!b) return a;
int gcd=exgcd(x,y,b,a%b);
int exx=y,exy=x-(a/b)*y;
x=exx,y=exy;return gcd;
}
代码现场手敲的,可能会错qwq
用处
扩欧的用处十分广泛,一般用于求线性同余方程中,用于求逆元过程中可以做到比快速幂更快······
计算\(ax+by=c\)的一般解
\(ax+by=c\)有无穷组解,扩欧计算出来的是其中的一个,我们称之为特解\((x_0,y_0)\),通过求出的特解,我们假设按大小排序,特解\((x_0,y_0)\)的下一组解为\((x_0+c,y_0+d)\),那么一定有:
\(a\cdot (x_0+c)+b\cdot (y_0+d)=c\)
\(ac=-bd\)
即$$\frac cd=-\frac ba=-\frac{\frac{b}{gcd(a,b)}}{\frac{a}{gcd(a,b)}}$$
所以有对于一般解\((x,y)\):\(x=x_0+k\cdot \frac{b}{gcd(a,b)};y=y_0-k\cdot \frac{a}{gcd(a,b)} ,k\in Z\)
同余
当且仅当\(m|(a-b)\)时,我们称\(a\)与\(b\)对模\(m\)同余,记作\(a\equiv b(mod\space m)\) (这里总视\(m>0\))
性质
①\(a\equiv a(mod\space m)\)
②对称性:若\(a\equiv b(mod \space m),\)则$ b\equiv a(mod\space m)$
③传递性:若\(a\equiv b (mod \space m),b\equiv c (mod \space m)\)则\(a\equiv c(mod \space m)\)
④同加同乘性:若\(a\equiv b(mod\space m),c\equiv d (mod \space m)\)则有
\(a\pm c(mod\space m)\equiv b\pm d(mod \space m),\)
\(ac(mod\space m)\equiv bd(mod \space m)\)
⑤若\(n|m,a\equiv b (mod \space m)\)则\(a\equiv b(mod\space n)\)
完全剩余系
对于一个正整数\(n\),如果一个剩余系包含了它所有可能的余数(大多数来讲为\(0,1,\ldots,n-1\)),那么这个剩余系被称为是模\(n\)的一个完全剩余系。记作\(Z_n\)
简化剩余系就是完全剩余系中与\(n\)互素的数,记作\(Z^*_n\)
线性同余方程
数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次.
即形如\(ax\equiv b(mod\space n)\)的方程\((n>0)\)
求解\(ax\equiv b(mod \space n)\)
关于方程\(ax\equiv b(mod\space n)\),当且仅当\(gcd(a,n)|b\)时有解。
(因为由方程可以得到:\(ax+kn=b\),
可以将此视为另一个方程,由裴蜀定理可得,当且仅当\(gcd(a,n)|b\)时此方程有解)
那么对于上面的方程$ax+kn=b,
\(令\)d=gcd(a,n)\(,则有\)d|b$
又因为\(d|a,d|n\),令\(a_0=\frac ad,n_0=\frac nd\)
有方程\(a_0x+n_0k=\frac bd\)
因为\(gcd(a_0,n_0)=1\),这个方程就可以由扩展欧几里得算法来求得
练习:青蛙的约会
题外话:裴蜀定理的证明
设\(d=gcd(a,b)\),
则有\(d|a,d|b\),易得\(d|(ax+by)\),
故\(\forall x,y\in Z,\)有\(d|(ax+by)\),
则设\(s=(ax+by)\),使\(s\)为满足\(d|(ax+by)\)的最小正值,则有\(d|s\)
令\(q=\lfloor \frac a,s\rfloor,r=a\space mod\space s=a-qs,\)
\(r=a-qax-qby=(1-qx)a+(-qy)b\)
可以看出\(r\)也表示的是\(a,b\)的线性组合,
又因为\(0\leq r<s\),\(s\)又是满足\(d|(ax+by)\)的最小正值,
所以\(r=0\),则有\(s|a,\) 同理\(s|b\),则\(s|d\),
因此可得\(d=s\),命题得证。