裴蜀定理扩展欧几里得算法

本文主要是介绍裴蜀定理扩展欧几里得算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

裴蜀定理

也就是Bezout定理，对于任意整数a,b，存在一对整数x,y，满足$ax+by=gcd(a,b)$。
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。
裴蜀定理说明了对任何整数 a、b和它们的最大公约数 d ，关于未知数 x 和 y 的线性丢番图方程（称为裴蜀等式）。

证明：

• 若b=0时，此时迭代到算法的最后一步，显然存在一对整数，$x=1,y=0$，使得$a\ast 1+0\ast 0=gcd(a,0)$
• 若b>0时，则$gcd(a,b)=gcd(b,amodb)$，假设存在一对整数$x_1,y_1$，满足$b\ast x_1+(amodb)\ast y_1=gcd(b,amodb)$，因为$b\ast x_1+(amodb)\ast y_1=b\ast x_1+(a-a/b\ast b)y_1=a\ast y_1+b\ast (x_1-(a/b)\ast y_1)$
• 证毕

裴蜀定理是按照欧几里得算法的思路被证明的，并且同时给出了整数x和y的计算方法。这种计算方法被称为扩展欧几里得算法。

联立一下
$$\{\begin{array}{l}gcd=a\ast x+b\ast y\\ gcd=a\ast y_1+b\ast (x_1-(a/b)\ast y_1)\end{array}$$

可以得出
$$\{\begin{array}{l}x=y_1\\ y=x_1-(a/b)\ast y_1\end{array}$$

实现

int exgcd(int a,int b,int &x,int &y){if(b==0){x = 1,y = 0;return a;}int ans = exgcd(b,a%b,x,y);int z = y;y = x - (a/b)*z,x = z;return ans;
}

说明

上述程序求出的是一组特解$x_0,y_0$，并返回a,b的最大公约数d。

未完，待续…

这篇关于裴蜀定理扩展欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---