扩展欧几里得算法
有关 欧几里得算法，参考 辗转相除法
定理
如果 a, b \in \mathbb{N^+}，那么 (a, b) = s_na + t_n b
其中，s_n, t_n 是下面定义的递归序列的第 n 项
\begin{aligned}
s_0 = 1, t_0 = 0, \\
s_1 = 0, t_1 = 1, \\
\end{aligned}
且
s_j = s_{j-2} - q_{j-1}s_{j-1}, t_j = t_{j-2} - q_{j-1}t_{j-1}
其中 j=2, 3, \cdots, n，q_j 是欧几里得算法中的每一步的商。
证明
我们将证明：
r_j = s_ja + t_jb\ (j = 0, 1, \cdots, n)
因为 (a, b) = r_n，一旦上式成立，我们就有
(a, b) = s_na + t_n b
我们用 第二数学归纳法 来证明
对于 j = 0，有 a = r_0 = 1 \cdot a + 0 \cdot b = s_0 a + t_0 b，成立；
对于 j = 1， b = r_1 = 0 \cdot a + 1 \cdot b = s_1 a + t_1 b，成立；
现在假设
r_j = s_ja + t_jb
对于 j = 1, 2, \cdots, k-1 成立，那么，由欧几里得算法的第 k 步，我们有：
r_k = r_{k - 1} = r_{k - 1}q_{k - 1}
那么由归纳假设，得到：
\begin{aligned}
r_k =& (s_{k-2}a + t_{k-2}b) - (s_{k - 1}a + t_{k - 1}b) q_{k -1} \\
=& (s_{k-2} + s_{k-1}q_{k - 1})a - (t_{k - 2} + t_{k - 1})b \\
=& s_k a + t_k b \\
\end{aligned}
证毕；
Python 代码
def ext_euclid(a: int, b: int): s = [1, 0, 0] t = [0, 1, 0] q = [0, 0, 0] j = 0 while b != 0: q[(j + 1) % 3], r = divmod(a, b) if j > 1: s[j % 3] = s[(j - 2) % 3] - q[(j - 1) % 3] * s[(j - 1) % 3] t[j % 3] = t[(j - 2) % 3] - q[(j - 1) % 3] * t[(j - 1) % 3] a = b b = r j += 1 s[j % 3] = s[(j - 2) % 3] - q[(j - 1) % 3] * s[(j - 1) % 3] t[j % 3] = t[(j - 2) % 3] - q[(j - 1) % 3] * t[(j - 1) % 3] return a, s[j % 3], t[j % 3]
评论