欧几里得算法与扩展欧几里得算法

注:本节可以独立阅读,但同时也是 《具体数学》(原书第二版) 4.1 整除性 的旁注。

一个基本事实

记 $n = am + b$,其中 $n,m,a,b \in \mathbb Z$,则 $d$ 为 $m,n$ 的公因数当且仅当 $d$ 为 $m,b$ 的公因数。

证明:

充分性:

若 $d \mid m$,$d \mid n$ 则必有

$$
d \mid n-am \Leftrightarrow d \mid b
$$

又因为 $d \mid m$,所以 $d$ 为 $m,b$ 的公因数

必要性:

若 $d \mid m$,$d \mid b$ 则必有

$$
d \mid am + b \Leftrightarrow d \mid n
$$

故 $d \mid n, d\mid m$,即 $d$ 为 $m,n$ 的公因数。

Q.E.D.

由这个结论,我们能得出一个更强的结论:

$d$ 为 $m,n$ 的最大公因数当且仅当 $d$ 为 $m,b$ 的最大公因数。

证明:

由之前的结论:$m,n$ 的所有公因数所构成的集合必定等于 $m,b$ 所有公因数所构成的集合,即

$$
\{d \mid (d\mid m), (d\mid n)\} = \{d \mid (d\mid m), (d\mid b)\}
$$

对于每一个 $b = n-am, a\in \mathbb Z$ 都成立。

$$
\sup \{d \mid (d\mid m), (d\mid n)\} = \sup \{d \mid (d\mid m), (d\mid b)\}
$$

Q.E.D.

欧几里得算法

对于 $m, n \geq 0, m, n$ 不同时为零的两个数:

$$
\gcd(0,n) = n
$$

$$
\gcd(n,0) = n
$$

$$
\gcd(m,n) = \gcd(n \mod m, m), m > 0
$$

证明:

注意到

$$
n \mod m = n - m\lfloor n/m \rfloor
$$

$$
n = m\lfloor n/m \rfloor + (n\mod m)
$$

根据之前的引理:

$$
\gcd (n, m) = \gcd(m, n \mod m)
$$

$$
\gcd (m,n) = \gcd(n\mod m, m)
$$

由于在迭代过程中,值总是在变小,所以过程必定能结束。

欧几里得算法的程序实现

#include <iostream>

using namespace std;

int gcd(int m, int n) {
    if (!m) return n;
    return gcd(n % m, m);
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << "gcd: " << gcd(m, n) << endl;
    return 0;
}

关于负数的讨论:迭代过程中,绝对值一直在变小,所以过程必定能结束。虽然 C/C++ 中的取模和数学中的取模不一定完全一样,但是取模仍然意味着:

$$
a \text { mod' } b = a - kb, k \in \mathbb Z
$$

所以整个过程仍然是正确的,只不过最后可能相差一个符号,由于 $\gcd$ 恒正,我们顶多需要增加一个取绝对值的过程。

扩展欧几里得算法

扩展欧几里得主要研究下面这个式子:

$$
xm + yn = \gcd (m, n)
$$

试找出其的整数解 $(x, y)$。

我们可以发现,这个问题就是欧几里得算法的衍生产物。

温习欧几里得的迭代过程。我们分两部考虑这个问题

(1) 迭代终止:

当 $m = 0$ 时

$$
0*x + ny = n
$$

我们可以取

$$
x = 0, y = 1
$$

(2) 迭代还没有达到终止条件时:

$$
xm + yn = \gcd(m,n)
$$

取 $r = n \mod m$,作为欧几里得算法迭代时的额外产物,我们便可以得到一个类似的子问题:

$$
x'r + y'm = \gcd(r,m)
$$

注意到,我们已经证明了

$$
\gcd(m, n) = \gcd(r, m)
$$

$$
\begin{aligned}
&x'r + y'm = \gcd(m,n) \\
\Leftrightarrow~&x'(n - m\lfloor n/m\rfloor) + y'm = \gcd(m, n) \\
\Leftrightarrow~&(y'-\lfloor n/m\rfloor x')m + x'n = \gcd(m,n)
\end{aligned}
$$

所以,只要解决了我们的子问题,解出了 $x', y'$,我们就能算出 $x, y$:

$$
x = y'- \lfloor n/m \rfloor x'
$$

$$
y = x'
$$

由此,我们结束了迭代过程的描述。

扩展欧几里得的程序实现

#include <iostream>

using namespace std;

int exgcd(int m, int n, int &x, int &y) {
    if (!m) {
        x = 0; y = 1;
        return n;
    }
    int d = exgcd(n % m, m, x, y);
    int y1 = x;
    x = y - n / m * x;
    y = y1;
    return d;
}

int main() {
    int m, n;
    cin >> m >> n;
    int x, y;
    int d = exgcd(m, n, x, y);
    cout << "gcd: " << d << endl;
    cout << x << " * " << m << " + " << y << " * " << n << " = " << d << endl;
    return 0;
}

注意:虽然 C/C++ 中,整数除法不一定是向下取整,取模也不是数学定义的取模,但是不影响我们这样写的正确性。因为,我们在证明中用到的取模和向下取整,其实只需要下面的恒等式成立:

$$
m = n \lfloor m/n \rfloor + (m \mod n)
$$

而在 C/C++ 中:

$$
m = (m / n) * n + m \% n
$$

是一个等价结论,所以我们可以理所当然地使用 /% 符号进行运算替换。

下面是一些打表验证:

再者,是关于负数的讨论。前面提到了,普通的欧几里得算法对于负数可能导致一个符号的相反,而在这里,如果符号相反了,我们只需要对 $x, y, \gcd$ 都乘上一个负一即可。

此外,扩欧还蕴含了如下事实:对于 $m, n \in \mathbb N$,且不同是为零,我们总能找到 $x,y\in \mathbb Z$,使得 $xm+yn=\gcd(m,n)$。

Reference

最后修改:2022 年 03 月 05 日 06 : 27 PM
真的不买杯奶茶嘛....qwq