歐幾里得演算法

歐幾里得演算法

歐幾里得演算法用於查詢兩個數字 \(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 次，而除法方法僅用一次計算就完成了相同的操作。

正如您所見，這些方法做的事情是相同的，除法方法只是在同一次計算中進行了多次減法，從而更快地找到了最大公約數。