欧几里得算法与 Bézout 等式

1. 要解决的问题

枚举所有因数可以计算小整数的最大公约数，但整数很大时效率很低。欧几里得算法（Euclidean Algorithm）利用余数不断缩小问题。

扩展欧几里得算法（Extended Euclidean Algorithm）还会找出整数 $x,y$，使

$$ax+by=\gcd(a,b).$$

这组系数是理解模逆元的关键。

---

2. 核心递推式

设

$$a=qb+r,qquad 0\leq r<b.$$

因为 $r=a-qb$，能够同时整除 $a,b$ 的整数也一定整除 $r$；反过来，能够同时整除 $b,r$ 的整数也一定整除 $a=qb+r$。

因此两组公约数完全相同：

$$\gcd(a,b)=\gcd(b,r).$$

又因为 $r=a\bmod b$，可写成

$$\gcd(a,b)=\gcd(b,a\bmod b).$$

---

3. 完整例子：计算 $\gcd(48,18)$

第一次除法：

$$48=2 * 18+12.$$

所以

$$\gcd(48,18)=\gcd(18,12).$$

第二次除法：

$$18=1 * 12+6.$$

所以

$$\gcd(18,12)=\gcd(12,6).$$

第三次除法：

$$12=2 * 6+0.$$

余数为 0 时停止，最后一个非零余数是 6：

$$\gcd(48,18)=6.$$

---

4. Bézout 等式

Bézout 等式说明：对不全为 0 的整数 $a,b$，存在整数 $x,y$，使

$$ax+by=\gcd(a,b).$$

这里的 $x,y$ 称为 Bézout 系数。它们通常不是唯一的。

对前面的例子，将余数关系倒着回代：

$$6=18-1 * 12,$$

而

$$12=48-2 * 18.$$

代入得到

$$\begin{aligned} 6 &=18-(48-2 * 18) \\ &=3 * 18-48. \end{aligned}$$

因此可以取

$$x=-1,qquad y=3,$$

并验证

$$48 * (-1)+18 * 3=6.$$

---

5. 为什么它能产生模逆元

如果

$$\gcd(a,n)=1,$$

Bézout 等式给出

$$ax+ny=1.$$

两边模 $n$ 后，$ny$ 的余数为 0，因此

$$ax\equiv1\pmod n.$$

这说明 $x$ 就是 $a$ 在模 $n$ 下的一个乘法逆元。完整的等价关系将在模逆元中继续推导。

---

6. Python 验证

from math import gcd

print(gcd(48, 18))

预期输出：

6

程序验证具体输入，不替代递推式和 Bézout 等式的一般证明。

---

7. 自测

1. 为什么 $\gcd(a,b)=\gcd(b,a\bmod b)$？
2. 计算 $\gcd(99,78)$。
3. Bézout 系数是否唯一？
4. 为什么 $\gcd(a,n)=1$ 时能够得到 $ax\equiv1\pmod n$？

参考答案

1. 因为 $(a,b)$ 与 $(b,a\bmod b)$ 拥有相同的公约数集合。
2. $99=1 * 78+21$，$78=3 * 21+15$，$21=1 * 15+6$，$15=2 * 6+3$，$6=2 * 3$，所以最大公约数是 3。
3. 通常不唯一。
4. Bézout 等式给出 $ax+ny=1$，模 $n$ 后 $ny\equiv0$。

上一篇：整除、质数与最大公约数。
下一篇：同余与剩余类。