欧几里得算法

欧几里得算法

欧几里得算法用于查找两个数字 \(a\) 和 \(b\) 的最大公约数（gcd）。

最大公约数是能整除 \(a\) 和 \(b\) 而不留余数的最大数字。

该算法使用带余数的除法。它使用上一步的余数来设置下一步的计算。

继续阅读，了解如何手动、通过编程执行欧几里得算法，以及理解该算法的工作原理和原因。

数学术语

以下是描述欧几里得算法时需要了解的词语，以便理解本页的解释。

除数 (Divisor): 一个数字，我们可以用它来整除另一个数字，而不留余数。我们说 3 是 6 的除数，因为 \(6/3=2\)，没有余数（余数为 0）。

余数 (Remainder): 用一个数除以另一个数后剩下的部分。7 除以 3 等于 2，余数为 1。（所以 3 不是 7 的除数。）

公约数 (Common divisor): 对于数字 \(a\) 和 \(b\)，公约数是可以整除 \(a\) 和 \(b\) 而不产生余数的数字。18 和 12 的公约数是 2、3 和 6，因为 18 和 12 都可以被 2、3 和 6 整除，而没有余数。

最大公约数 (Greatest common divisor): 公约数中最大的一个。18 和 12 的最大公约数是 6，因为它是公约数 2、3 和 6 中最大的一个。

最大公约数在数论领域以及用于加密信息的密码学中都有应用。

手动演练

为了理解欧几里得算法的工作原理，以及如何编写其代码，我们首先手动运行它来找出 \(120\) 和 \(25\) 的最大公约数。

为此，我们使用带余数的除法。

步骤 1: 我们开始用 \(120\) 除以 \(25\)

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \end{aligned} \end{equation} \]

\(25\) 能在 \(120\) 中容纳多少次？是 4 次，对吧？\(4 \cdot 25\) 等于 100。我们通过从 120 中减去 100 来得到余数 20。

步骤 2: 我们在下一步中使用上一步的余数 20 来除以 25

\[ \begin{equation} \begin{aligned} 25 & = 1 \cdot 20 + 5 \end{aligned} \end{equation} \]

我们可以在 25 中容纳 20 一次。我们通过从 25 中减去 20 来得到余数 5。

步骤 3: 在下一步计算中，我们将 20 除以之前的余数 5

\[ \begin{equation} \begin{aligned} 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

我们得到余数 0，这意味着计算已完成。

\(120\) 和 \(25\) 的最大公约数是 \(5\)。

欧几里得算法的实现

要使用除法找到最大公约数，我们将继续运行该算法，直到计算出的余数为 \(0\)。

这相当于说，我们只要 \(b\) 不等于 0 就继续运行该算法。这就是为什么 b != 0 是下面 while 循环的条件。

def gcd_division(a, b):
    while b != 0:
        remainder = a % b
        print(f"{a} = {a//b} * {b} + {remainder}")
        a = b
        b = remainder
    return a

a = 120
b = 25
print("The Euclidean algorithm using division:\n")
print(f"The GCD of {a} and {b} is: {gcd_division(a, b)}")

原始欧几里得算法

与我们上面使用的除法不同，2000 多年前在《几何原本》中描述的原始欧几里得算法使用减法。

使用减法而不是除法速度较慢，但除法和减法方法都使用相同的数学原理。

这只需几行即可证明。

数字 \(a\) 和 \(b\) 有一个最大公约数 \(x\)。

这意味着 \(a\) 和 \(b\) 都可以这样分解：

\[ \begin{equation} \begin{aligned} a & = k \cdot x \\ b & = l \cdot x \end{aligned} \end{equation} \]

分解后，从 \(a\) 中减去 \(b\) 会得到一个非常有趣的结果：

\[ \begin{equation} \begin{aligned} a-b & = k \cdot x - l \cdot x \\ & = (k-l) \cdot x \end{aligned} \end{equation} \]

我们可以看到，\(a\) 和 \(b\) 的最大公约数（\(x\)) 也是 \(a\) 和 \(b\) 之间差值 \(a-b\) 的最大公约数！

这个原理是欧几里得算法工作的根本原因，它使其成为可能。

使用减法查找最大公约数

根据上述原理，即 \(a\) 和 \(b\) 之间的差值也具有相同的最大公约数，我们可以使用减法来查找最大公约数，就像欧几里得的原始算法那样。

让我们使用减法来查找 \(120\) 和 \(25\) 的最大公约数。

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \end{aligned} \end{equation} \]

根据已经描述的数学原理，数字 \(120\)、\(25\) 和 \(95\) 都共享相同的最大公约数。

这意味着我们可以通过从 \(95\) 中减去 \(25\) 来进一步简化我们的问题。

\[ \begin{equation} \begin{aligned} 95 - 25 & = 70 \end{aligned} \end{equation} \]

如果我们继续这样做，总是取上一步中最小的两个数字并找出它们之间的差值，我们会得到这些计算：

\[ \begin{equation} \begin{aligned} 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

当差值为 \(0\) 时，使用减法的欧几里得算法就完成了。

在倒数第二次计算中，我们看到 \(120\) 和 \(25\) 的最大公约数是 \(5\)。

现在我们已经学会了如何用手计算最大公约数（减法），在编程语言中实现它就更容易了。

使用减法的欧几里得算法实现

要使用减法找到最大公约数，我们将继续运行该算法，直到 \(a\) 和 \(b\) 之间的差值为 \(0\)，正如我们刚刚看到的。

这相当于说，我们只要 \(a\) 和 \(b\) 的值不同就继续运行该算法。这就是为什么 a != b 是下面 while 循环的条件。

def gcd_subtraction(a, b):
    while a != b:
        if a > b:
            print(f"{a} - {b} = {a-b}")
            a = a - b
        else:
            print(f"{b} - {a} = {b-a}")
            b = b - a
    return a

a = 120
b = 25
print("The Euclidean algorithm using subtraction:\n")
print(f"The GCD of {a} and {b} is: {gcd_subtraction(a, b)}")

比较减法和除法方法

为了更好地理解除法方法在查找最大公约数方面的优势，以及这些方法是如何相似的，我们将

1. 使用减法找到 \(120\) 和 \(25\) 的最大公约数。
2. 使用带余数的除法找到 \(120\) 和 \(25\) 的最大公约数。
3. 比较减法和除法方法。

1. 使用减法

使用减法查找 \(120\) 和 \(25\) 的最大公约数

\[ \begin{equation} \begin{aligned} 120 - 25 & = 95 \\ 95 - 25 & = 70 \\ 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned} \end{equation} \]

使用减法，当差值为 \(0\) 时，算法结束。

在倒数第二次计算中，我们看到 \(120\) 和 \(25\) 的最大公约数是 \(5\)。

注意 \(25\) 和 \(5\) 需要被减去很多次，才能找到 GCD。

2. 使用除法

使用带余数的除法查找 \(120\) 和 \(25\) 的最大公约数如下所示：

\[ \begin{equation} \begin{aligned} 120 & = 4 \cdot 25 + 20 \\ 25 & = 1 \cdot 20 + \underline{\textbf{5}} \\ 20 & = 4 \cdot 5 + 0 \end{aligned} \end{equation} \]

使用除法，当余数为 \(0\) 时，欧几里得算法就完成了。

之前的余数 \(5\) 是 \(120\) 和 \(25\) 的最大公约数。

3. 比较

看看上面提到的减法和除法方法。

为了更清楚地看到除法计算与减法计算基本上是相同的，我们可以这样写带余数的除法计算：

\[ \begin{equation} \begin{aligned} 120 - 4 \cdot 25 & = 20 \\ 25 - 1 \cdot 20 & = \underline{\textbf{5}} \\ 20 - 4 \cdot 5 & = 0 \end{aligned} \end{equation} \]

使用减法，\(25\) 总共从 \(120\) 中减去了 4 次，而除法方法仅用一步就完成了。

类似地，减法方法将 5 减去了 4 次，而除法方法仅用一次计算就完成了相同的操作。

正如您所见，这些方法做的事情是相同的，除法方法只是在同一次计算中进行了多次减法，从而更快地找到了最大公约数。