欧几里得算法

欧几里得算法

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

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

该算法使用带余除法。它将前一步的余数用于设置下一步的计算。

继续阅读以了解欧几里得算法如何手动执行、如何使用编程实现，以及了解算法如何以及为何真正起作用。

数学术语

以下是描述欧几里得算法的词汇，您需要了解这些词汇才能理解本页面上的解释。

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

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

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

最大公约数: 公约数中最大的那个。18 和 12 的最大公约数是 6，因为它是公约数 2、3 和 6 中最大的那个。

最大公约数在数论领域和密码学中用于加密消息。

手动运行

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

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

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

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

我们可以在 \(120\) 中放入多少个 \(25\)? 是 \(4\) 次，对吧? \(4 \cdot 25\) 是 \(100\)。我们将 \(100\) 从 \(120\) 中减去得到余数 \(20\)。

步骤 2: 我们在下一步中使用先前的余数 \(20\) 来除以 \(25\)

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

我们可以在 \(25\) 中放入一个 \(20\)。我们将 \(20\) 从 \(25\) 中减去得到余数 \(5\)。

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

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

我们得到 \(0\) 作为余数，这意味着我们完成了计算。

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

欧几里得算法的实现

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

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

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} \]

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

\[ \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\) 之差也具有相同的最大公约数，我们可以使用减法来求最大公约数，就像欧几里得最初的算法一样。

让我们使用减法来求 \(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\) 的值不同，就继续运行该算法是一样的。这就是为什么下面 while 循环中的条件为 a != b。

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} \]

使用减法，从 \(120\) 中减去 \(25\) 总共 \(4\) 次，而除法方法只用一步就能做到。

类似地，减法方法总共减去 \(5\) \(4\) 次，而除法方法只用一次计算就能做到。

如您所见，两种方法都做着同样的事情，只是除法方法在同一次计算中做了许多减法，因此它能更快地找到最大公约数。