初等数论-Base-2(扩展欧几里得算法，同余，线性同余方程，(附：裴蜀定理的证明))

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了初等数论-Base-2(扩展欧几里得算法，同余，线性同余方程，(附：裴蜀定理的证明))，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3407字，纯文字阅读大概需要5分钟。

内容图文

我们接着上面的欧几里得算法说

扩展欧几里得算法

扩展欧几里德算法是用来在已知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%b),\)

令\(ax+by=gcd(a,b)=gcd(b,a \space mod\space b)=c,\)
而

\[bx'+(a\space mod\space b)y'=ax+by\]

又因为\((a\space mod\space b)=a-\lfloor\frac ab\rfloor b\)

得\[bx'+ay'-\lfloor\frac ab\rfloor by'=ax+by\]

于是我们可以得到递归过程中层与层之间传递的式子：

\[x=y',y=(x'-\lfloor\frac ab\rfloor y');\]

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\)，命题得证。

内容总结

以上是互联网集市为您收集整理的初等数论-Base-2(扩展欧几里得算法，同余，线性同余方程，(附：裴蜀定理的证明))全部内容，希望文章能够帮你解决初等数论-Base-2(扩展欧几里得算法，同余，线性同余方程，(附：裴蜀定理的证明))所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---