07 扩展欧几里得算法
学习目标
学完这一节，你应该能够：
* 理解扩展欧几里得算法比普通欧几里得算法多求了什么；
* 理解递归出口为什么取 x=1,y=0x=1,y=0x=1,y=0；
* 理解递归返回的 x1,y1x_1,y_1x1 ,y1 分别表示什么；
* 一步一步推出回溯公式；
* 看懂并独立写出扩展欧几里得算法；
* 用扩展欧几里得算法求乘法逆元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 普通欧几里得算法能求什么
普通欧几里得算法利用：
gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b) gcd(a,b)=gcd(b,amodb)
不断递归，最终得到：
gcd(a,b)\gcd(a,b) gcd(a,b)
例如：
gcd(48,18)=6\gcd(48,18)=6 gcd(48,18)=6
普通欧几里得算法能够告诉我们最大公约数是 6。
但是裴蜀定理还告诉我们：
> 一定存在整数 x,yx,yx,y，使：
ax+by=gcd(a,b)ax+by=\gcd(a,b) ax+by=gcd(a,b)
对于：
a=48,b=18a=48,\qquad b=18 a=48,b=18
除了想知道：
gcd(48,18)=6\gcd(48,18)=6 gcd(48,18)=6
我们还可能想知道：
> 到底是哪一组 x,yx,yx,y，能够使 48x+18y=648x+18y=648x+18y=6？
扩展欧几里得算法就是用来做这件事的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 扩展欧几里得算法到底要返回什么
我们希望函数输入 a,ba,ba,b 后，不仅得到：
g=gcd(a,b)g=\gcd(a,b) g=gcd(a,b)
还同时求出两个整数 x,yx,yx,y，使：
ax+by=g\boxed{ax+by=g} ax+by=g
也就是：
ax+by=gcd(a,b)\boxed{ax+by=\gcd(a,b)} ax+by=gcd(a,b)
因此扩展欧几里得算法同时要得到：
* 最大公约数 ggg；
* 裴蜀系数 xxx；
* 裴蜀系数 yyy。
下面先假设 a>0,b≥0a>0,b\ge0a>0,b≥0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 先看递归出口为什么这样写
普通欧几里得算法最后一定会到：
gcd(a,0)\gcd(a,0) gcd(a,0)
并且：
gcd(a,0)=a\gcd(a,0)=a gcd(a,0)=a
扩展欧几里得算法此时还要找到 x,yx,yx,y，满足：
ax+0y=aax+0y=a ax+0y=a
最简单的选择是：
x=1,y=0x=1,\qquad y=0 x=1,y=0
因为：
a×1+0×0=aa\times1+0\times0=a a×1+0×0=a
所以递归出口写成：
这里的 x=1,y=0x=1,y=0x=1,y=0 不是需要死记的规定，而是为了让：
ax+by=gcd(a,b)ax+by=\gcd(a,b) ax+by=gcd(a,b)
在 b=0b=0b=0 时仍然成立。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 递归调用以后，我们到底得到了什么
设：
r=a mod br=a\bmod b r=amodb
普通欧几里得算法把：
gcd(a,b)\gcd(a,b) gcd(a,b)
转成：
gcd(b,r)\gcd(b,r) gcd(b,r)
所以扩展欧几里得算法也递归求：
exgcd(b,r)\operatorname{exgcd}(b,r) exgcd(b,r)
假设这次递归已经求出了：
x1,y1x_1,y_1 x1 ,y1
根据扩展欧几里得算法的目标，它们满足：
bx1+ry1=gcd(b,r)bx_1+ry_1=\gcd(b,r) bx1 +ry1 =gcd(b,r)
而欧几里得算法已经证明：
gcd(b,r)=gcd(a,b)\gcd(b,r)=\gcd(a,b) gcd(b,r)=gcd(a,b)
设：
g=gcd(a,b)g=\gcd(a,b) g=gcd(a,b)
于是递归返回以后，我们知道：
bx1+ry1=gbx_1+ry_1=g bx1 +ry1 =g
注意：
> x1,y1x_1,y_1x1 ,y1 是针对下一层的两个数 b,rb,rb,r 的系数。
当前这一层需要的是针对 a,ba,ba,b 的系数 x,yx,yx,y。
所以接下来要把 rrr 换回由 a,ba,ba,b 表示的形式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 回溯公式怎样一步一步得到
由带余除法：
a=qb+ra=qb+r a=qb+r
所以：
r=a−qbr=a-qb r=a−qb
递归返回时已经知道：
bx1+ry1=gbx_1+ry_1=g bx1 +ry1 =g
把：
r=a−qbr=a-qb r=a−qb
代入：
bx1+(a−qb)y1=gbx_1+(a-qb)y_1=g bx1 +(a−qb)y1 =g
展开：
bx1+ay1−qby1=gbx_1+ay_1-qby_1=g bx1 +ay1 −qby1 =g
把含 aaa 的部分和含 bbb 的部分分别整理：
ay1+b(x1−qy1)=***_1+b(x_1-qy_1)=g ay1 +b(x1 −qy1 )=g
而当前这一层希望得到：
ax+by=gax+by=g ax+by=g
对比两个式子：
ax+by=gax+by=g ax+by=g
ay1+b(x1−qy1)=***_1+b(x_1-qy_1)=g ay1 +b(x1 −qy1 )=g
可以得到：
x=y1\boxed{x=y_1} x=y1
y=x1−qy1\boxed{y=x_1-qy_1} y=x1 −qy1
又因为整数除法中：
q=⌊ab⌋q=\left\lfloor\frac ab\right\rfloor q=⌊ba ⌋
所以 C++ 中写成：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 为什么这种回溯可以一直返回到最开始
递归最深处先解决：
gcd(d,0)\gcd(d,0) gcd(d,0)
并得到：
d×1+0×0=dd\times1+0\times0=d d×1+0×0=d
然后回到上一层。
上一层利用刚才推导出的：
x=y1x=y_1 x=y1
y=x1−qy1y=x_1-qy_1 y=x1 −qy1
把“下一层的系数”转换成“当前层的系数”。
再往上一层时，又做同样的转换。
因此：
> 每返回一层，系数就从更小的一组数转换成上一层那组数的系数。
一直回到最开始的 a,ba,ba,b 后，就得到：
ax+by=gcd(a,b)ax+by=\gcd(a,b) ax+by=gcd(a,b)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 用具体数字完整跟踪一次
求：
gcd(48,18)\gcd(48,18) gcd(48,18)
同时求 x,yx,yx,y，使：
48x+18y=648x+18y=6 48x+18y=6
欧几里得算法：
48=2×18+1248=2\times18+12 48=2×18+12
18=1×12+618=1\times12+6 18=1×12+6
12=2×6+012=2\times6+0 12=2×6+0
所以：
gcd(48,18)=6\gcd(48,18)=6 gcd(48,18)=6
7.1 最深层：(6,0)(6,0)(6,0)
取：
x=1,y=0x=1,\qquad y=0 x=1,y=0
因为：
6×1+0×0=66\times1+0\times0=6 6×1+0×0=6
7.2 回到 (12,6)(12,6)(12,6)
这一层：
12=2×6+012=2\times6+0 12=2×6+0
下一层返回：
x1=1,y1=0x_1=1,\qquad y_1=0 x1 =1,y1 =0
所以：
x=y1=0x=y_1=0 x=y1 =0
y=x1−2y1=1y=x_1-2y_1=1 y=x1 −2y1 =1
检查：
12×0+6×1=612\times0+6\times1=6 12×0+6×1=6
7.3 回到 (18,12)(18,12)(18,12)
这一层：
18=1×12+618=1\times12+6 18=1×12+6
下一层返回：
x1=0,y1=1x_1=0,\qquad y_1=1 x1 =0,y1 =1
所以：
x=y1=1x=y_1=1 x=y1 =1
y=x1−1×y1=−1y=x_1-1\times y_1=-1 y=x1 −1×y1 =−1
检查：
18×1+12×(−1)=618\times1+12\times(-1)=6 18×1+12×(−1)=6
7.4 回到 (48,18)(48,18)(48,18)
这一层：
48=2×18+1248=2\times18+12 48=2×18+12
下一层返回：
x1=1,y1=−1x_1=1,\qquad y_1=-1 x1 =1,y1 =−1
所以：
x=y1=−1x=y_1=-1 x=y1 =−1
y=x1−2y1=1−2×(−1)=3y=x_1-2y_1=1-2\times(-1)=3 y=x1 −2y1 =1−2×(−1)=3
检查：
48×(−1)+18×3=−48+54=648\times(-1)+18\times3=-48+54=6 48×(−1)+18×3=−48+54=6
因此一组裴蜀系数是：
x=−1,y=3\boxed{x=-1,\qquad y=3} x=−1,y=3
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. C++ 模板
调用：
结束以后：
g=gcd(a,b)g=\gcd(a,b) g=gcd(a,b)
并且：
ax+by=gax+by=g ax+by=g
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 用扩展欧几里得算法求逆元
上一章已经知道：
如果：
gcd(a,m)=1\gcd(a,m)=1 gcd(a,m)=1
那么 aaa 在模 mmm 下存在逆元。
裴蜀定理告诉我们，一定存在整数 x,yx,yx,y，使：
ax+my=1ax+my=1 ax+my=1
扩展欧几里得算法可以把这一组 x,yx,yx,y 实际求出来。
由：
ax+my=1ax+my=1 ax+my=1
移项：
ax−1=−myax-1=-my ax−1=−my
所以：
m∣(ax−1)m\mid(ax-1) m∣(ax−1)
于是：
ax≡1(modm)ax\equiv1\pmod m ax≡1(modm)
所以这个 xxx 就是 aaa 在模 mmm 下的一个逆元代表。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 例子：求 3 在模 7 下的逆元
扩展欧几里得算法可以得到：
3×(−2)+7×1=13\times(-2)+7\times1=1 3×(−2)+7×1=1
所以：
3×(−2)≡1(mod7)3\times(-2)\equiv1\pmod7 3×(−2)≡1(mod7)
因此：
−2-2 −2
是一个逆元代表。
通常希望答案满足：
0≤x<70\le x<7 0≤x<7
因为：
−2≡5(mod7)-2\equiv5\pmod7 −2≡5(mod7)
所以标准非负代表是：
5\boxed{5} 5
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 为什么负数可以变成标准非负余数
如果求得：
x=−2x=-2 x=−2
模数是：
m=7m=7 m=7
那么：
−2≡5(mod7)-2\equiv5\pmod7 −2≡5(mod7)
因为：
−2−5=−7-2-5=-7 −2−5=−7
是 7 的倍数。
C++ 中常写：
这是因为 C++ 中负数 % 的结果可能仍然为负。
先加一个 mmm，再取一次模，就可以把结果调整到：
0≤x<m0\le x<m 0≤x<m
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 小练习
练习 1
扩展欧几里得算法比普通欧几里得算法多求出了什么？
练习 2
为什么递归出口可以取：
x=1,y=0x=1,\qquad y=0 x=1,y=0
练习 3
已知：
bx1+ry1=gbx_1+ry_1=g bx1 +ry1 =g
并且：
r=a−qbr=a-qb r=a−qb
推导当前层的 x,yx,yx,y。
练习 4
若扩欧求得逆元代表为 −3-3−3，模数为 11，标准非负代表是多少？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 答案
练习 1
除了求出 gcd(a,b)\gcd(a,b)gcd(a,b)，还求出整数 x,yx,yx,y，使：
ax+by=gcd(a,b)ax+by=\gcd(a,b) ax+by=gcd(a,b)
练习 2
因为当 b=0b=0b=0 时：
gcd(a,0)=a\gcd(a,0)=a gcd(a,0)=a
而：
a×1+0×0=aa\times1+0\times0=a a×1+0×0=a
练习 3
代入：
bx1+(a−qb)y1=gbx_1+(a-qb)y_1=g bx1 +(a−qb)y1 =g
整理：
ay1+b(x1−qy1)=***_1+b(x_1-qy_1)=g ay1 +b(x1 −qy1 )=g
所以：
x=y1x=y_1 x=y1
y=x1−qy1y=x_1-qy_1 y=x1 −qy1
练习 4
−3≡8(mod11)-3\equiv8\pmod{11} −3≡8(mod11)
所以答案是 8。
