GCD - 数论中基本概念的深入探讨

• 最大公约数概述
  • 定义1 - GCD
  • 定义2 - 互质
  • 命题1
• 欧几里得算法
  • 欧几里得算法的几何视角
• 扩展欧几里得算法
  • 定理1
  • 命题2
  • 定理2

最大公约数概述

数字 $12$ 和 $18$ 的共同因数为 1、2、3 和 6，其中 6 是最大的。对于任何一对非零整数 a 和 b，都可以构造出这样一组共同因数。这个集合至少会包括数字 1，因为它是所有整数的因数。由于这个集合是有限的，它将始终具有最大值。

定义1 - GCD

考虑两个整数 a 和 b，它们都不为零。a 和 b 之间的共同因数集合有一个最大元素，我们将其记作 d。这个 d 被称为 a 和 b 的最大公约数（GCD）。我们用 $d = gcd(a, b)$ 来表示。

该方程表示 d 是能够同时整除 a 和 b 而不留下余数的最大整数。

示例。 $gcd(24, 52) = 4$，$gcd(9, 27) = 9$，$gcd(14, 35) = 7$，$gcd(15, 28) = 1$。

定义2 - 互质

两个整数 a 和 b 被称为 相对质数 或 互质，如果 $gcd(a, b) = 1$。

示例。 $gcd(15, 28) = 1$，$gcd(15, 14) = 1$，$gcd(21, 40) = 1$。

备注。 如果 $a \neq 0$，那么 $gcd(a,0) = a$。

然而，我们并不定义 $gcd(0, 0)$。这是因为任何整数，不论多大，都可以整除 0，所以不存在最大因数。

因此，当我们对 $gcd(a, b)$ 做出声明时，通常会指定至少 a 和 b 中有一个是非零的。

换句话说，每当我们写 $gcd(a, b)$ 时，隐含的假设是 a 和 b 中至少有一个是非零的。

备注。 我们已观察到 $gcd(24, 44) = 4$。因此，24 和 44 不是互质的。然而，如果我们用它们的 GCD 4 除以 24 和 44，我们分别得到 6 和 11。这两个数是互质的。

这是合乎逻辑的，因为我们是用它们的 GCD，最大共同因数来除这些数。因此，得到的数字除了 1 之外没有共同因数，使它们成为互质数。

命题1

如果 a 和 b 是整数，且 $d = gcd(a, b)$，那么 $gcd(\frac{a}{d}, \frac{b}{d}) = 1$。

证明。 如果 $c = gcd(\frac{a}{d}, \frac{b}{d})$，那么 $c \mid \frac{a}{d}$ 且 $c \mid \frac{b}{d}$。这意味着存在整数 $k_1$ 和 $k_2$，使得 $a = ck_1$ 和 $b = ck_2$，这告诉我们 $a = cdk_1$ 和 $b = cdk_2$。所以，$cd$ 是 $a$ 和 $b$ 的一个共同因数。由于 $d$ 是最大公约数，而且 $cd \geq d$，我们必须有 $c = 1$。

欧几里得算法

欧几里得算法是数论中一种非常有价值的工具，早在《欧几里得几何原本》的第七卷中作为 命题2 被提及。它的主要优点是能够在不需要因式分解的情况下计算最大公约数（gcd）。这个特性在密码学中尤其重要，因为数字往往有数百位，并且难以因式分解。

我们来计算 $gcd(123, 456)$。考虑以下计算：

$$456 = 3 · 123 + 87$$

$$123 = 1 · 87 + 36$$

$$87 = 2 · 36 + 15$$

$$36 = 2 · 15 + 6$$

$$6 = 2 · 3 + 0$$

在考虑 456 和 123 的质因数分解时，我们发现 $gcd$ 是最后一个非零的余数，即 3。以下是我们遵循的过程：

首先，我们将较小的数字 123 除以较大的 456，得到余数 87。接下来，我们将数字 123 和 87 左移，再次进行除法，并得到余数 36。我们重复这一 “左移并除” 方法，直到得到余数为 0。

让我们试另一个例子。我们计算 $gcd(119, 259)$。考虑以下计算：

$$259 = 2 · 119 + 21$$

$$119 = 5 · 21 + 14$$

$$21 = 1 · 14 + 7$$

$$14 = 2 · 7 + 0$$

再次地，最后一个非零的余数是 gcd，即 $gcd$ 是 $7$。为什么这有效？我们先展示为什么 $7$ 是一个共同因数。

最后一行的余数为 0 表示 $7 \mid 14$。由于 $7 \mid 7$ 和 $7 \mid 14$，倒数第二行表示 $7 \mid 21$，因为 21 是 7 和 14 的线性组合。现在向上挪动一行。我们刚才证明了 $7 \mid 14$ 且 $7 \mid 21。由于119是21和14的线性组合，我们推导出 $7 \mid 119$。最后，移动到最上一行，我们看到 $7 \mid 259$，因为259是119和21的线性组合，这两者都是7的倍数。因此，由于 $7 \mid 119$ 和 $7 \mid 259$，我们证明了7是119和259` 的一个共同因数。

我们现在想展示 7 是最大的共同因数。让 d 是 119 和 259 的任何一个因数。最上一行表明，21 是两个数 259 和 119 的线性组合（即 $259 − 2 · 119$），是 d 的倍数。接着，转到第二行。119 和 21 两者都是 d 的倍数，因此 14 也必须是 d 的倍数。第三行告诉我们，由于 $d \mid 21$ 并且 $d \mid 14$，我们必须有 $d \mid 7$。特别的，$d \leq 7$，因此 7 是最大公约数，正如我们所说的。我们还证明了额外的事实，即任何共同因数必须能整除 7。

欧几里得算法。 设 a 和 b 为非负整数，并假设 $b \neq 0$。我们做以下计算：

$$a = q_1b + r_1, 其中 0 \leq r_1 < b$$

$$b = q_2r_1 + r_2, 其中 0 \leq r_2 < r_1$$

$$r_1 = q_3r_2 + r_3, 其中 0 \leq r_3 < r_2$$

$$\vdots$$

$$r{n−3} = q{n−1}r{n−2} + r{n−1}, 其中 0 \leq r{n−1} < r{n−2}$$

$$r{n−2} = q{n}r_{n−1} + 0$$

最后一个非零余数，即 $r_{n−1}$，等于 $gcd(a,b)$。

欧几里得算法的几何视角

假设我们想计算 $gcd(48, 21)$。从平面 $(x,y)$ 中的点 $(48, 21)$ 开始。

首先，向左移动 21 的增量，直到达到或超过直线 $y = x$。在这个例子中，我们迈出了两步的 21，到达 $(6,21)$。接着，向下移动 6（两个坐标中较小的那个）的增量，直到达到或超过直线 $y = x$。在这里，我们进行了三步的 6，到达 $(6, 3)$。接下来，向左移动 3 的增量。经过一步，我们抵达 $(3, 3)$，这个点在直线 $y = x$ 上。$gcd$ 即为 x 坐标（也是 y 坐标）。

在每一系列的移动中，步数与欧几里得算法中的 商 相对应，而 余数 则是最后一步超出直线 $y = x$ 的金额。

扩展欧几里得算法

欧几里得算法揭示了一个有趣且实用的事实：两个数字 $a$ 和 $b$ 的最大公约数 $gcd$ 可以表示为 a 和 b 的 线性组合。换句话说，存在整数 x 和 y 使得 $gcd(a, b) = ax + by$。

这里是一些示例：

$$3 = gcd(456, 123) = 456 · 17 − 123 · 63$$

$$7 = gcd(259, 119) = 259 · 6 − 119 · 13$$

获取 x 和 y 的方法称为 扩展欧几里得算法。有时这些也被称为贝祖等式的系数。

一旦你使用欧几里得算法得出 $gcd(a, b)$，就有一种简单且非常直接的方法来实现扩展欧几里得算法。下面我将通过一个例子展示它是如何工作的。

扩展欧几里得算法基于欧几里得算法，该算法反复进行欧几里得除法，直至余数为零。扩展欧几里得算法同样跟踪每次除法的商，并使用它们以递归方式计算系数 x 和 y。

以下是该算法如何工作的示例。假设我们要为 a = 36 和 b = 10 找到 gcd 和贝祖等式的系数。我们可以使用表格来跟踪步骤：

前四列和欧几里得算法相同。最后两列的计算如下：

• 在第一行，我们初始化 x = 0 和 y = 1。
• 在每一行之后，我们用公式更新 x 和 y：

$$x = x{\text{prev}} - q \cdot y{\text{prev}}$$

$$y = y{\text{prev}} - q \cdot x{\text{prev}}$$

其中 $x{\text{prev}}$ 和 $y{\text{prev}}$ 是前一行的 x 和 y 的值，q 是当前行的商。

当余数 r 为零时，算法停止。最后一个非零余数是 a 和 b 的 gcd，对应的 x 和 y 值是贝祖等式的系数。在这个例子中，我们有：

$$gcd(36, 10) = 2$$

$$2 = (-1) \cdot 36 + (4) \cdot 10$$

定理1

设 a 和 b 为整数，且至少有一个 a 或 b 非零。存在整数 x 和 y，可通过扩展欧几里得算法找到，使得

$$gcd(a, b) = ax + by.$$

证明。 考虑能够表示为 $ax + by$ 的整数集合 $S$，其中 x 和 y 是整数。由于 a、b、-a 和 -b 都是 $S$ 的元素，我们可以得出 $S$ 至少包含一个正整数。

设 d 为 $S$ 中最小的正整数（根据 哲学的良序律）。既然 d 是 $S$ 的一个元素，我们可以写 $d = ax_0 + by_0$ 为某些整数 $x_0$ 和 $y_0$。

现在，我们声称 a 和 b 都是 d 的倍数，使 d 成为 a 和 b 的共同因数。为证明这一点，我们写 $a = dq + r$，其中 q 和 r 是整数，且 $0 \leq r < d$。

通过代入「d」的表达式，我们得到：

$$r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0q) + b(-y_0q)$$

由于 r 是 $S$ 的元素，我们可以得出 r 也是一个正整数。然而，由于 d 是 $S$ 中最小的正元素，且 $0 \leq r < d$，我们必须有 $r = 0$。

这意味着 d 整除 a。类似地我们可以证明 d 整除 b。因此，d 是 a 和 b 的共同因数。

命题2

如果 a 和 b 是整数，并且不都是 0，且 e 是一个正整数，则

$$gcd(ea, eb) = e \cdot gcd(a, b).$$

证明。 根据定理1，存在整数 x、y，使得 $gcd(a, b) = ax + by$。乘以 e，得到 $e \cdot gcd(a,b) = eax + eby$。如果 d 是 ea 和 eb 的一个共同因数，那么 d 整除 $e \cdot gcd(a, b)$。因此，$d \leq e \cdot gcd(a, b)$。由于 $e \cdot gcd(a, b)$ 是 ea 和 eb 的一个共同因数，它必须是 gcd，如所声称的。

定理2

设 $n \geq 2$，并设 $a_1,a_2,...,a_n$ 为整数（至少有一个必须为非零）。则存在整数 $x_1,x_2,...,x_n$ 使得

$$gcd(a_1,a_2,...,a_n)=a_1x_1 +a_2x_2 +···+a_nx_n.$$

证明。 我们将通过数学归纳法来证明该定理。根据定理1，该结果对于 $n = 2$ 是正确的。假设对于 $n = k$ 是正确的。然后

$$gcd(a_1,a_2,··· ,a_k) = a_1y_1 +a_2y_2 +···+a_ky_k$$

对于一些整数 $y_1, y_2, . . . , y_k$。但是，

$$gcd(a_1, a2, . . . , a{k+1}) = gcd(gcd(a_1, a_2, . . . , ak), a{k+1})$$

$$= gcd(a_1, a_2, . . . , ak)x + a{k+1}y$$

对于某些整数 x 和 y，根据定理1。因此，

$$gcd(a_1,a2,...,a{k+1}) = (a_1y_1 +a_2y_2 +···+a_kyk)x + a{k+1}y$$

$$= a_1(xy_1) + a_2(xy_2) + · · · + a_k(xyk) + a{k+1}y_{k+1}$$，这是所需的结果，其中 $x_i = xyi$，适用于 $1 \leq i \leq k$，$x{k+1} =y$。因此，该结果对于 $n = k + 1$ 成立。通过归纳法，该结果对于所有正整数 $n \geq 2$ 成立。

• 原文链接： github.com/thogiti/thogi...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～