首页 > 笔记 > 扩展欧几里德算法总结

扩展欧几里德算法总结

获得更好的阅读效果,请到这里

引入

对于一类特殊的丢番图方程,它是恒定有整数解的。它的形式就是:

这其实就是贝祖定理的主要内容。接下来我们来证明一下:

注:下文

,则。由于整除的性质,,则有。设的最小正值,则

所以也是的一个线性组合。由于的线性组合的最小值,,可得。则,同理,则,因此,证毕。

而已知,求的一组可行解的算法叫做扩展欧几里德算法。

流程

我们可以试着求解一下

1.当,显然可得

2.当时:

由欧几里德算法,我们可得

则:

由于

我们可以把它给拆开:

由于恒等定理

我们就可以得到了求解的方法。以上的思想是递归定义的,因为的求解过程中,一定会有,所以递归会结束。

时,即为最大公因数。这时只需要保证的系数即即可,的取值是没有影响的,不妨设

代码

 

应用

求解丢番图方程

丢番图方程就是引入中的例子,形如一类的方程。我们可以先把等式两边都除以,如果不能整除则就是无解。

那么现在就变成了为了满足扩欧的条件使,可以将等式两遍同时除以c,得到。这样就可以直接利用exgcd求出的值,然后再乘回去就可以了。

求出来可行解了之后再将不断不断,解仍然成立。

 

求解模线性方程

结论

同余方程 对于未知数有解,当且仅当。且方程有解时,方程有 个解。

解法一

求解方程 相当于求解方程

,假如整数 ,满足 (用扩展欧几里德得出)。如果 ,则方程,两边乘以,(因为 ,所以能够整除),得到

所以 的一个解,所以 的解。

的一个解为 ,且方程的个解分别为

解法二

首先看一个简单的例子:

解得

由此可以发现一个规律,就是解的间隔是.

那么这个解的间隔是怎么决定的呢?

如果可以设法找到第一个解,并且求出解之间的间隔,那么就可以求出模的线性方程的解集了.

我们设解之间的间隔为.

那么有

;

;

两式相减,得到:

;

也就是说就是的倍数,同时也是的倍数,即的公倍数.为了求出,我们应该求出的最小公倍数,此时对应的是最小的.

的最大公约数为,那么的最小公倍数为.

;

所以.

因此解之间的间隔就求出来了.

 

求解乘法的逆元

定义

乘法在模p意义下的逆元是什么呢?

可以通俗的理解一下。在模运算法则中,我们只说了

 

最后的那个究竟是什么呢?

其实

因为

所以

由于的特殊性,我们可以求出它。

解法

所以

同余方程,如果 ,则方程只有唯一解。

在这种情况下,如果 ,同余方程就是

这时称求出的 的对模 乘法的逆元。

对于同余方程 的求解就是求解方程

。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×