在本讲中，我们将深入研究欧几里得算法的一种扩展，这一算法不仅可以计算最大公约数，还能找到满足贝祖等式（Bézout equation）的整数解。
在介绍拓展欧几里得算法之前，让我们先来了解一下贝祖等式。对于两个整数 $a$ 和 $b$，存在整数 $x$ 和 $y$ 使得它们满足如下等式：
$$
ax + by = \gcd(a, b)
$$
这个等式称为贝祖等式，其中 $\gcd(a, b)$ 是 $a$ 和 $b$ 的最大公约数。拓展欧几里得算法的目标就是找到这样的整数 $x$ 和 $y$。
拓展欧几里得算法在使用欧几里得算法计算最大公约数的同时，通过逆向推导，找到满足贝祖等式的整数解。在欧几里得算法中，我们只关心每次迭代的余数 $r_i$，而不关心商 $q_i$；而拓展算法中利用 $q_i$ 逆向求出贝祖等式，可谓是废物利用了。
让我们回忆一下欧几里得算法：
$$
a = bq_0 + r_0
$$
$$
b = r_0q_1 + r_1
$$
$$
...
$$
$$
r_{i-2} = r_{i-1}q_{i} + r_i
$$
$$
...
$$
$$
r_{n-2} = r_{n-1}q_{n} + r_n
$$
我们会不断迭代直到 $r_n = 0$，而此时 $r_{n-1}= \gcd(a,b)$，有：
$$
r_{n-2} = \gcd(a,b) q_{n}
$$
$$
r_{n-3} = r_{n-2} q_{n-1} + \gcd(a,b)
$$
$$
...
$$
$$
a = bq + r
$$
其中所有 $q_i$ 都是已知的。因此，我们可以不断展开，将 $r, ..., r_{n-2}$ 表示为 $a$ 和 $b$ 的线性组合，最终将 $\gcd(a,b)$ 表示为 $a$ 和 $b$ 的线性组合，得到贝祖等式。
下面使用迭代和递归两种方法推导。
首先，我们将每次迭代得到的余数写为 $a$ 和 $b$ 的线性组合。对于第 $i$ 次迭代得到的余数 $r_i$，设整数 $x_i$ 和 $y_i$ 使得以下等式成立：
$$
x_i a + y_i b=r_i
$$
因为 $r_{n-1}=\gcd(a,b)$，因此有
$$
x_{n-1} a + y_{n-1} b=\gcd(a,b)
$$
因此, $(x_{n-1}, y_{n-1} )$ 就是满足贝祖等式的 $(x,y)$。我们需要做的就是迭代的计算出它们。
从式子 $r_{i-2} = r_{i-1}q_{i} + r_i$ 我们可以得到：
$$
r_i = r_{i-2} - r_{i-1}q_{i}
$$
将 $r_{i-2}$ 和 $r_{i-1}$ 展开为 $a$ 和 $b$ 的线性组合，得到：
$$
r_i = (x_{i-2} - x_{i-1}q_{i}) a + (y_{i-2} - y_{i-1}q_{i}) b
$$
因此，我们得到了 $(x_i, y_i)$ 与 $(x_{i-2},x_{i-1},y_{i-2},y_{i-1})$ 的迭代关系：
$$
x_i = x_{i-2} - x_{i-1}q_{i}
$$
$$
y_i = y_{i-2} - y_{i-1}q_{i}
$$
有了迭代关系，接下来，我们需要确定初始条件。对于第一步迭代，有：
$$
r_0 = a - q_0b
$$
也就是说 $x_0 = 1$, $y_0 = -q_0$, 因此有：
$$
1 = x_{-2} -q_0 x_{-1}
$$
$$
-q_0 = y_{-2} -q_0 y_{-1}
$$
因此，我们可以得到初始条件 $(x_{-2}, x_{-1}, y_{-2}, y_{-1}) = (1, 0, 0, 1)$
然后在使用欧几里得算法时不断迭代 $(x_i, y_i)$，
$$
x_i = x_{i-2} - x_{i-1}q_{i}
$$
$$
y_i = y_{i-2} - y_{i-1}q_{i}
$$
最终得到的 $(x_{n-1}, y_{n-1})$ 就是贝祖等式中的 $(x,y)$。
下面我们计算使得 $a=30$ 和 $b=24$ 满足贝祖等式的整数 $x$ 和 $y$：
$$
ax + by = \gcd(a, b)
$$
-
第一步：初始化 $(x_{-2}, x_{-1}, y_{-2}, y_{-1}) = (1, 0, 0, 1)$。
-
第二步：运用欧几里得除法，得到
$$
30 = 1 \cdot 24 + 6
$$
这里 $(q_0, r_0) = (1, 6)$，代入 $(x_i, y_i)$ 迭代等式，有：
$$
x_0 = 1 - 1 \times 0 = 1
$$
$$
y_0 = 0 - 1 \times 1 = -1
$$
此时 $x_i a + y_i b=r_i$，等式左边为 $30-24$，右边 $6$，等式成立。
- 第三步：余数 $r=6$ 不为零，用 $b$ 替换 $a$, $r$ 替换 $b$，继续运用欧几里得除法，得到
$$
24 = 4 \cdot 6 + 0
$$
这里 $(q_1, r_1) = (4, 0)$, 此时余数为0，停止迭代。得到最大公约数 $\gcd(30,24)=6$, 而 $(x, y) = (x_0, y_0)=(1, -1)$.
- 第四步：得到满足贝祖等式的系数 $(x, y) =(1, -1)$，贝祖等式为：
$$
a - b = 6
$$
要求 $x, y$ 满足 $x\cdot a+y\cdot b=gcd(a, b)$ 。
当 $b = 0$ 时，显然 $x=1, y=0$ ；
当 $b\neq 0$ 时，有 $gcd(a, b)=gcd(b, a% b)$ 。对于左边， $gcd(a, b)=ax+by$ ，对于右边， $gcd(b, a% b)=bx_1+(a% b)\cdot y_1=bx_1+(a-(a//b)\cdot b)\cdot y_1=ay_1+b(x_1-(a//b)\cdot y_1)$, 左右对应有： $x=y_1, y=(x_1-(a//b)\cdot y_1)$。推毕。
让我们用Python来实现拓展欧几里得算法：
def extended_euclidean_algorithm(a, b):
x1, y1, x2, y2 = 1, 0, 0, 1
while b:
q = a // b
a, b = b, a % b
x1, x2 = x2, x1 - q * x2
y1, y2 = y2, y1 - q * y2
return a, x1, y1
# 示例
num1 = 30
num2 = 24
gcd_result, x, y = extended_euclidean_algorithm(num1, num2)
print(f'{num1} 和 {num2} 的最大公约数是 {gcd_result}')
print(f'满足贝祖等式的整数解为：{num1}*{x} + {num2}*{y} = {gcd_result}')def ext_gcd(a, b):
if b == 0:
return 1, 0
else:
x, y = ext_gcd(b, a%b)
x, y = y, x - (a//b) * y
return x, y拓展欧几里得算法的应用非常广泛，其中一些主要的应用场景包括：
-
乘法逆元： 拓展欧几里得算法最主要的用途是计算模 N 乘法逆元，具体过程见下一讲。
-
RSA算法： 在RSA非对称加密算法中，拓展欧几里得算法用于生成私钥，确保其满足一定的数学关系。
-
同余方程求解： 在数论中，拓展欧几里得算法常用于解决同余方程，即形如 $ax \equiv 1 \pmod{m}$ 的方程，其中 $a$ 和 $m$ 互质。
这一讲，我们介绍了贝祖等式和拓展欧几里得算法。拓展欧几里得算法有着广泛应用，学好它，可以为我们日后深入学习零知识证明奠定基础。