【数论·同余】扩展欧几里得Exgcd算法与线性同余方程求解

本文主要是介绍【数论·同余】扩展欧几里得Exgcd算法与线性同余方程求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

扩展欧几里得算法Exgcd

Exgcd算法内容

给定$a,b,c,d$,求解$ax+by=gcd(a,b)$中的任意正数解$(x,y)$

---

Exgcd求解一组整数解

我们可以根据裴蜀定理，证明方程一定有解。

由于欧几里得算法$gcd(a,b)=gcd(b,a\%b)$,则有：
$$ax+by=bx+(a\%b)\ast y$$

用除法代替取模，则：$$ax+by=b{x}^{\prime }+y^{\prime }(a-[a/b]\ast b)$$

通过乘法分配律和结合律的运算可得：$$ax+by=a{y}^{\prime }+b(x^{\prime }-[a/b]\ast y^{\prime })$$

其中， x ′ x'

这篇关于【数论·同余】扩展欧几里得Exgcd算法与线性同余方程求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---