扩展欧几里得算法

CreateTime 2021-09-21
UpdateTime 2021-10-03

有关 欧几里得算法,参考 辗转相除法

定理

如果 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, nq_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 = 1b = 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]

参考资料