扩展欧几里得算法(EXGCD)学习笔记
Chinshyo
2021-03-15 22:31:23
# 0.前言
相信大家对于欧几里得算法都已经很熟悉了。再学习数论的过程中,我们会用到扩展欧几里得算法(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;//返回最大公约数
}
}
```