07 扩展欧几里得算法
学习目标
学完这一节，你应该能够：
- 理解扩展欧几里得算法比普通欧几里得算法多求了什么；
- 理解递归出口为什么取 x=1,y=0；
- 理解递归返回的 x1,y1 分别表示什么；
- 一步一步推出回溯公式；
- 看懂并独立写出扩展欧几里得算法；
- 用扩展欧几里得算法求乘法逆元。
1. 普通欧几里得算法能求什么
普通欧几里得算法利用：
gcd(a,b)=gcd(b,amodb)
不断递归，最终得到：
gcd(a,b)
例如：
gcd(48,18)=6
普通欧几里得算法能够告诉我们最大公约数是 6。
但是裴蜀定理还告诉我们：
一定存在整数 x,y，使：
ax+by=gcd(a,b)
对于：
a=48,b=18
除了想知道：
gcd(48,18)=6
我们还可能想知道：
到底是哪一组 x,y，能够使 48x+18y=6？
扩展欧几里得算法就是用来做这件事的。
2. 扩展欧几里得算法到底要返回什么
我们希望函数输入 a,b 后，不仅得到：
g=gcd(a,b)
还同时求出两个整数 x,y，使：
ax+by=g
也就是：
ax+by=gcd(a,b)
因此扩展欧几里得算法同时要得到：
- 最大公约数 g；
- 裴蜀系数 x；
- 裴蜀系数 y。
下面先假设 a>0,b≥0。
3. 先看递归出口为什么这样写
普通欧几里得算法最后一定会到：
gcd(a,0)
并且：
gcd(a,0)=a
扩展欧几里得算法此时还要找到 x,y，满足：
ax+0y=a
最简单的选择是：
x=1,y=0
因为：
a×1+0×0=a
所以递归出口写成：
if (b == 0) {
x = 1;
y = 0;
return a;
}
这里的 x=1,y=0 不是需要死记的规定，而是为了让：
ax+by=gcd(a,b)
在 b=0 时仍然成立。
4. 递归调用以后，我们到底得到了什么
设：
r=amodb
普通欧几里得算法把：
gcd(a,b)
转成：
gcd(b,r)
所以扩展欧几里得算法也递归求：
exgcd(b,r)
假设这次递归已经求出了：
x1,y1
根据扩展欧几里得算法的目标，它们满足：
bx1+ry1=gcd(b,r)
而欧几里得算法已经证明：
gcd(b,r)=gcd(a,b)
设：
g=gcd(a,b)
于是递归返回以后，我们知道：
bx1+ry1=g
注意：
x1,y1 是针对下一层的两个数 b,r 的系数。
当前这一层需要的是针对 a,b 的系数 x,y。
所以接下来要把 r 换回由 a,b 表示的形式。
5. 回溯公式怎样一步一步得到
由带余除法：
a=qb+r
所以：
r=a−qb
递归返回时已经知道：
bx1+ry1=g
把：
r=a−qb
代入：
bx1+(a−qb)y1=g
展开：
bx1+ay1−qby1=g
把含 a 的部分和含 b 的部分分别整理：
ay1+b(x1−qy1)=g
而当前这一层希望得到：
ax+by=g
对比两个式子：
ax+by=g
ay1+b(x1−qy1)=g
可以得到：
x=y1
y=x1−qy1
又因为整数除法中：
q=⌊ba⌋
所以 C++ 中写成：
x = y1;
y = x1 - (a / b) * y1;
6. 为什么这种回溯可以一直返回到最开始
递归最深处先解决：
gcd(d,0)
并得到：
d×1+0×0=d
然后回到上一层。
上一层利用刚才推导出的：
x=y1
y=x1−qy1
把“下一层的系数”转换成“当前层的系数”。
再往上一层时，又做同样的转换。
因此：
每返回一层，系数就从更小的一组数转换成上一层那组数的系数。
一直回到最开始的 a,b 后，就得到：
ax+by=gcd(a,b)
7. 用具体数字完整跟踪一次
求：
gcd(48,18)
同时求 x,y，使：
48x+18y=6
欧几里得算法：
48=2×18+12
18=1×12+6
12=2×6+0
所以：
gcd(48,18)=6
7.1 最深层：(6,0)
取：
x=1,y=0
因为：
6×1+0×0=6
7.2 回到 (12,6)
这一层：
12=2×6+0
下一层返回：
x1=1,y1=0
所以：
x=y1=0
y=x1−2y1=1
检查：
12×0+6×1=6
7.3 回到 (18,12)
这一层：
18=1×12+6
下一层返回：
x1=0,y1=1
所以：
x=y1=1
y=x1−1×y1=−1
检查：
18×1+12×(−1)=6
7.4 回到 (48,18)
这一层：
48=2×18+12
下一层返回：
x1=1,y1=−1
所以：
x=y1=−1
y=x1−2y1=1−2×(−1)=3
检查：
48×(−1)+18×3=−48+54=6
因此一组裴蜀系数是：
x=−1,y=3
8. C++ 模板
long long exgcd(long long a, long long b,
long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1, y1;
long long g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
调用：
long long x, y;
long long g = exgcd(a, b, x, y);
结束以后：
g=gcd(a,b)
并且：
ax+by=g
9. 用扩展欧几里得算法求逆元
上一章已经知道：
如果：
gcd(a,m)=1
那么 a 在模 m 下存在逆元。
裴蜀定理告诉我们，一定存在整数 x,y，使：
ax+my=1
扩展欧几里得算法可以把这一组 x,y 实际求出来。
由：
ax+my=1
移项：
ax−1=−my
所以：
m∣(ax−1)
于是：
ax≡1(modm)
所以这个 x 就是 a 在模 m 下的一个逆元代表。
10. 例子：求 3 在模 7 下的逆元
扩展欧几里得算法可以得到：
3×(−2)+7×1=1
所以：
3×(−2)≡1(mod7)
因此：
−2
是一个逆元代表。
通常希望答案满足：
0≤x<7
因为：
−2≡5(mod7)
所以标准非负代表是：
5
11. 为什么负数可以变成标准非负余数
如果求得：
x=−2
模数是：
m=7
那么：
−2≡5(mod7)
因为：
−2−5=−7
是 7 的倍数。
C++ 中常写：
x = (x % m + m) % m;
这是因为 C++ 中负数 % 的结果可能仍然为负。
先加一个 m，再取一次模，就可以把结果调整到：
0≤x<m
12. 小练习
练习 1
扩展欧几里得算法比普通欧几里得算法多求出了什么？
练习 2
为什么递归出口可以取：
x=1,y=0
练习 3
已知：
bx1+ry1=g
并且：
r=a−qb
推导当前层的 x,y。
练习 4
若扩欧求得逆元代表为 −3，模数为 11，标准非负代表是多少？
13. 答案
练习 1
除了求出 gcd(a,b)，还求出整数 x,y，使：
ax+by=gcd(a,b)
练习 2
因为当 b=0 时：
gcd(a,0)=a
而：
a×1+0×0=a
练习 3
代入：
bx1+(a−qb)y1=g
整理：
ay1+b(x1−qy1)=g
所以：
x=y1
y=x1−qy1
练习 4
−3≡8(mod11)
所以答案是 8。
有帮助，赞一个