欧几里得算法的描述及证明

欧几里得算法

算法 E.（欧几里得算法） 给定两个正整数\(m\)和\(n\)，求它们的最大公因子，即能够同时整除\(m\)和\(n\)的最大正整数。
EO. [确保 \(m \geq{n}\)] 如果\(m<n\)，交换 \(m \leftrightarrow n\)。
E1. [求余数] 以\(n\)除\(m\)并令\(r\)为所得余数。（我们将有 \(0 \leq r \le n\)。）
E2. [余数为零？] 若 \(r=0\)，算法结束，\(n\)即为答案。
E3. [减少] 置 \(m \leftarrow {n}\)，\(n \leftarrow {r}\)，并返回步骤 E1。 \(\blacksquare\)

python 版实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

def GCD(m: int, n: int) -> int:
    # E0
    if m < n:
        m, n = n, m
    while True:
        # E1
        r = m % n
        # E2
        if r == 0:
            return n
        # E3
        m, n = n, r
    raise

定理 1 如果\(a\)，\(b\)，\(m\)和\(n\)为整数，且\(c|a\)，\(c|b\)，则\(c|(ma+bn)\)。

证明 因为\(c|a\)且\(c|b\)，存在整数\(e\)和\(f\)，使得\(a=ce\)，\(b=cf\)。因此，\(ma+nb=mce+ncf=c(me+nf)\)。从而，我们知道\(c|(ma+nb)\)。\(\blacksquare\)

定理 2 令\(a\)，\(b\)，\(c\)是整数，那么\((a+cb,b)=(a,b)\)。

证明 \(a\)，\(b\)，\(c\)是整数。我们将证明\(a\)，\(b\)的公因子与\(a+cb\)，\(b\)的公因子相同。这就证明了\((a+cb,b)=(a,b)\)。令\(e\)是\(a\)，\(b\)的公因子。由定理 1我们有\(e|(a+cb)\)，所以\(e\)是\(a+cb\)和\(b\)的公因子。如果\(f\)是\(a+cb\)和\(b\)的公因子，那么由定理 1我们有\(f\)整除\((a+cb)-cb=a\)，所以\(f\)是\(a\)，\(b\)的公因子。因此\((a+cb,b)=(a,b)\)。\(\blacksquare\)

定理 3（欧几里得算法） 整数\(a \geq b > 0\)，令\(r_0=a\)，\(r_1=b\)。如果我们做带余除法得到\(r_j=r_{j}q_{j+1}+r_{j+2}\)，且\(0<r_{j+2}<r_{j+1}\)，\(j=0,1,2,\cdots,n-2\)且有\(r_{n+1}=0\)，那么\((a,b)=r_n\)，即最后一个非零余数。

证明 \(a\)，\(b\)是正整数，其中\(a \geq b\)，令\(r_0=a\)，\(r_1=b\)。那么通过带余除法，我们求得

\[ \begin{aligned} r_0 &= r_{1}q_{1}+r_{2} && 0 \leq r_2 \le r_1, \\ r_1 &= r_{2}q_{2}+r_{3} && 0 \leq r_3 \le r_2, \\ &\vdots \\ r_{j-2} &= r_{j-1}q_{j-1}+r_{j} && 0 \leq r_j \le r_{j-1}, \\ &\vdots \\ r_{n-4} &= r_{n-3}q_{n-3}+r_{n-2} && 0 \leq r_{n-2} \le r_{n-3}, \\ r_{n-3} &= r_{n-2}q_{n-2}+r_{n-1} && 0 \leq r_{n-1} \le r_{n-2}, \\ r_{n-2} &= r_{n-1}q_{n-1} + r_{n} && 0 \leq r_{n} \le r_{n-1}, \\ r_{n-1} &= r_{n}q_{n}. \end{aligned} \]

假设最终一定会有一个余数为零，正是因为余数组成的序列为\(a=r_0 \geq r_1 \ge r_2 \ge \cdots \geq 0\)，序列包含的项的个数不会大于\(a\)（因为每个余数都是整数）。由定理 2，我们得到

\[ \begin{aligned} (a,b) &=(r_0,r_1)=(r_1,r_2)=(r_2,r_3) \\ &=\cdots \\ &=(r_{n-2},r_{n-1})=(r_{n-1},r_n)=(r_n,0)=r_n \end{aligned} \]

因此\((a,b)=r_n\)，即最后一个非零余数。\(\blacksquare\)

扩充的欧几里得算法

算法 E.（扩充的欧几里得算法） 给定两个正整数\(m\)和\(n\)，我们计算它们的最大公因子\(d\)和两个整数\(a\)和\(b\)，使得\(am+bn=d\)。
E1. [初始化] 置 \(a' \leftarrow b \leftarrow 1\)，\(a \leftarrow b' \leftarrow 0\)，\(c \leftarrow m，d \leftarrow n\)。
E2. [循环] 设\(q\)和\(r\)分别是\(c\)除以\(d\)的商和除数。（我们有\(c=qd+r\)，且 \(0 \leq r < d\)。）
E3. [余数为 0？] 如果\(r=0\)，算法终止；在此情况下，我们如愿地有\(am+bn=d\)。
E4. [循环] 置\(c \leftarrow d，d \leftarrow r\)，\(t \leftarrow a'\), \(a' \leftarrow a\)，\(a \leftarrow t - qa\)，\(t \leftarrow b'\)，\(b' \leftarrow b\)，\(b \leftarrow t-qb\)，并返回 E2。\(\blacksquare\)

python 版实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def extendedGCD(m: int, n: int) -> tuple[int, int, int]:
    # E1
    a_successor = b = 1
    a = b_successor = 0
    c = m
    d = n
    while True:
        # E2
        q, r = c // d, c % d
        # E3
        if r == 0:
            return d, a, b
        # E4
        c = d
        d = r
        t = a_successor
        a_successor = a
        a = t - q * a
        t = b_successor
        b_successor = b
        b = t - q * b
    raise

定理 4 令\(a\)，\(b\)为正整数，那么

\[(a,b)=s_{n}a+t_{n}b\]

其中\(s_{n}\)，\(t_n\)是下面定义的递归序列的第\(n\)项

\[ \begin{aligned} s_0=1,\quad t_0&=0, \\ s_1=0,\quad t_1&=1. \end{aligned} \]

且

\[ s_{j}=s_{j-2}-q_{j-1}s_{j-1},\quad t_j=t_{j-2}-q_{j-1}t_{j-1} \]

其中\(j=2,3,\cdots,n\)，\(q_j\)是欧几里得算法中每一步的商。

证明 我们将证明

\[r_j=s_{j}a+t_{j}b \quad (j=0,1,\cdots,n) \tag{2.1}\]

因为\((a,b)=r_{n}\)，一旦等式 (2.1) 成立，我们就有

\[(a,b)=s_{n}a+t_{n}b\]

我们用第二数学归纳法来证明 (2.1)。对于\(j=0\)，有\(a=r_0=1 \cdot a + 0 \cdot b=s_{0}a+t_{0}b\)。因此对于\(j=0\)成立。类似地，\(b=r_1=0 \cdot a + 1 \cdot b=s_{1}a+t_{1}b\)，所以 (2.1) 对于\(j=1\)成立。

现在假设

\[ r_j=s_ja+t_jb \]

对于\(j=1,2,\cdots,k-1\)成立。那么，由欧几里得算法的第\(k\)步，我们有

\[r_k=r_{k-2}-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}q_{k-1})b \\ &= s_{k}a+t_{k}b. \end{aligned} \]

这就完成了证明。\(\blacksquare\)

递归版算法数学定义及实现

递归版欧几里得算法数学定义：

递归版欧几里得算法 python 版实现：

1
2
3
4
5
6

def GCD(m: int, n: int) -> int:
    if m < n:
        m, n = n, m
    if n == 0:
        return m
    return GCD(n, m % n)

递归版扩充的欧几里得算法数学定义：

递归版扩充的欧几里得算法 python 版实现：

1
2
3
4
5
6
7

def extendedGCD(m: int, n: int) -> tuple[int, int, int]:
    def _extendedGCD(m, n, a, a_successor, b, b_successor):
        if n == 0:
            return m, a, b
        q = m // n
        return _extendedGCD(n, m % n, a_successor, a - q * a_successor, b_successor, b - q * b_successor)
    return _extendedGCD(m, n, 1, 0, 0, 1)