美文网首页
欧几里得算法解线性方程

欧几里得算法解线性方程

作者: 摇摆苏丹 | 来源:发表于2021-01-17 19:52 被阅读0次

引言

对于线性方程ax+by=n, a,b \in \mathbb{N+},x,y \in \mathbb{Z}，可以使用裴蜀定理验证该方程是否有解，当获得一个特解后，可以利用线性方程定理获得其他解。现在的问题就是，如果要解一个线性方程，如何获得第一个特解？

解法

如果n是gcd(a,b)的倍数，即n=z*gcd(a,b)，求得线性方程ax+by=gcd(a,b)的解(x,y)后，(zx,zy)就是原方程的解。因此只需要考察方程ax+by=gcd(a,b)的解。
对于欧几里得算法的递归式展开后的各行，都有如下表的规律：
\begin{array}{c|c} a=q_1b+r1 & r_1=a-q_1b \\ b=q_2r_1+r_2 & r_2=b-q_2(a-q_1b)=-q_2a+(1+q_1q_2)b\\ r1=q_3r_2+r_3 & r_3=r_1-q_3r_2=(1+q_2q_3)a-(q_1+q_3+q_1q_2q_3)b\\ \cdots & \cdots \\ r_{n-2}=q_{n}r_{n-1}+r_{n} & r_n=sa+tb \end{array}
由上表可知，r_n = gcd(a,b)总能表示为a,b的线性组合，上述过程中的s,t就是线性方程的解x,y。

例子

求22x+60y=gcd(22,60)的整数解。
x,y的地位相同，故可以置换x,y的位置，设a=60,b=22，则有60x+22y=gcd(22,60)。
\begin{array}{c|c|c} 60=2*22+16&a=2b+16&16=a-2b\\ 22=1*16+6&b=1*(a-2b)+6&6=-a+3b\\ 16=2*6+4&a-2b=2*(-a+3b)+4&4=3a-8b\\ 6=1*4+2&-a+3b=1*(3a-8b)+2&2=-4a+11b\\ 4=2*2+0&\cdots&\cdots \end{array}
最后得到-4a+11b=2=gcd(22,60)，故线性方程的一个特解是(-4,11)。利用线性方程定理，得通解为：
(x_1+k\frac{b}{g},y_1-k\frac{a}{g}), g=gcd(a,b) \to (-4+11k,11-30k)
可以验证一些特解如：(7,-19),(18,-49)都是正确的。

相关文章

网友评论

      本文标题：欧几里得算法解线性方程

      本文链接：https://www.haomeiwen.com/subject/oxczaktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|欧几里得算法解线性方程|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！