扩展欧几里得算法(EXGCD)学习笔记

相信大家对于欧几里得算法都已经很熟悉了。再学习数论的过程中,我们会用到扩展欧几里得算法(exgcd),大家一定也了解过。这是本蒟蒻在学习扩展欧几里得算法过程中的思考与探索过程。

1.Bézout定理

扩展欧几里得算法利用归纳法,证明了Bézout定理。

Bézout定理:对于任意整数 \(a\),\(b\) ,存在一对整数 \(x\),\(y\),满足 \(ax+by=gcd(a,b)\)
在扩展欧几里得的算法中,我们求出 \(x\),\(y\) 的值。

2.证明 2.1 \(gcd\)

首先,我们来看一下 \(gcd\) 函数

int gcd (int a, int b) { if(b == 0) return a; else return gcd(b, a % b); }

在第二行,也就是递归终止时,\(b=0\)\(a=gcd(a,b)\)。 我们可以发现存在一对整数 \(x\),\(y\) 满足条件 \(ax+by=gcd(a,b)\)
将已知的值代入可得:\(ax+b*0=gcd(a,b)\)
\(a=gcd(a,b)\)
\(gcd(a,b)*x=gcd(a,b)\)
\(y\)在终止时可取任意值,\(x=1\)

2.2归纳法

我们在2.1中得到了 \(b=0\) 时的解。现在,我们用归纳法一步步得到最终解。当 \(b>0\) 时,我们假设 \(b*x\) 满足条件 \(b*x+(a\,mod\,b*y)gcd(b,a\,mod\,b)\)(代入的值也正是我们平时进行gcd的转移方程)
\(∵ bx+(a\,mod\,b)y=bx+[a-b(a/b)]y\)
\(∴ bx+(a\,mod\,b)y=bx+ay-by(a/b)\)
\(∴ bx+(a\,mod\,b)y=ay+bx-by(a/b)\)
\(∴ bx+(a\,mod\,b)y=ay+b[x-(a/b)y]\)
\(x_1=y\), \(y_1=x-(a\,mod\,b)y\),再代入已得到的式子,就能得到:
\(ax_1+by_1=gcd(a,b)\),所以可以得出Bézout定理成立。

3.代码实现 3.1思路简述

我们的代码在截止条件上与 \(gcd\) 相同,都是 if(b == 0)时停止递归。我们在此基础上再改变 \(x\)\(y\) 的值。

3.2参考代码及注释

大部分都按照前面的推导过程

int exgcd(int a, int b, int &x, int &y) { //x,y的初始值无关 if(b == 0) { x = 1, y = 0;//改变x,y的值(y可取任意值) return a; } else { int tmp = exgcd(b, a % b, x, y);//保存下一次的最大公约数 int z = x; //存储上一次的x y = x; //及上文中的y1 x = z - y * (a / b); //及上文中的x_1 return tmp;//返回最大公约数 } }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyxsdg.html