輾轉相除法

輾轉相除法是求最大公因數很有效率的方法. 首先我們介紹輾轉相除法的原理.

Lemma 1.3.1   若 a, b $\in$ $\mathbb {N}$ 且 a = bh + r, 其中 h, r $\in$ $\mathbb {Z}$, 則 gcd(a, b) = gcd(b, r).

証 明. 假設 d₁ = gcd(a, b) 且 d₂ = gcd(b, r). 我們證明 d₁| d₂ 且 d₂| d₁, 因而可利用 Proposition 1.1.3(2) 以及 d₁, d₂ 皆為正數得證 d₁ = d₂.

因 d₁| a 且 d₁| b 利用 Corollary 1.1.2 我們知 d₁| a - bh = r. 因為 d₁| b, d₁| r 且 d₂ = gcd(b, r) 故由 Proposition 1.2.5 知 d₁| d₂. 另一方面, 因為 d₂| b 且 d₂| r 故 d₂| bh + r = a. 因此可得 d₂| d₁. $\qedsymbol$

Lemma 1.3.1 告訴我們當 a > b > 0 時, 要求 a, b 的最大公因數我們可以先將 a 除以 b 所得餘數若為 r, 則 a, b 的最大公因數等於 b 和 r 的最大公因數. 因為 0$\le$r < b < a, 所以當然把計算簡化了. 接著我們就來看看輾轉相除法. 由於 gcd(a, b) = gcd(- a, b) 所以我們只要考慮 a, b 都是正整數的情況.

Theorem 1.3.2 (The Euclidean Algorithm)   假設 a, b $\in$ $\mathbb {N}$ 且 a > b. 由除法原理我們知存在 h₀, r₀ $\in$ $\mathbb {Z}$ 使得

a = bh₀ + r₀,    其中 0$\le$r₀ < b.

若 r₀ > 0, 則存在 h₁, r₁ $\in$ $\mathbb {Z}$ 使得

b = r₀h₁ + r₁,    其中 0$\le$r₁ < r₀.

若 r₁ > 0, 則存在 h₂, r₂ $\in$ $\mathbb {Z}$ 使得

r₀ = r₁h₂ + r₂,    其中 0$\le$r₂ < r₁.

如此繼續下去直到 r_n = 0 為止. 若 n = 0 (即 r₀ = 0), 則 gcd(a, b) = b. 若 n$\ge$1, 則 gcd(a, b) = r_{n - 1}.

証 明. 首先注意若 r₀$\ne$ 0, 由於 r₀ > r₁ > r₂ > ... 是嚴格遞減的, 因為 r₀ 和 0 之間最多僅能插入 r₀ - 1 個正整數, 所以我們知道一定會有 n$\le$r₀ 使得 r_n = 0.

若 r₀ = 0, 即 a = bh₀, 故知 b 為 a 之因數, 得證 b 為 a, b 的最大公因數. 若 r₀ > 0, 則由 Lemma 1.3.1 知

gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = ^... = gcd(r_{n - 1}, r_n) = gcd(r_{n - 1}, 0) = r_{n - 1}.

$\qedsymbol$

現在我們來看用輾轉相除法求最大公因數的例子.

Example 1.3.3   我們求 a = 481 和 b = 221 的最大公因數. 首先由除法原理得 481 = 2 ^. 221 + 39, 知 r₀ = 39. 因此再考慮 b = 221 除以 r₀ = 39 得 221 = 5 ^. 39 + 26, 知 r₁ = 26. 再以 r₀ = 39 除以 r₁ = 26 得 39 = 1 ^. 26 + 13, 知 r₂ = 13. 最後因為 r₂ = 13 整除 r₁ = 26 知 r₃ = 0, 故由 Theorem 1.3.2 知 gcd(481, 221) = r₂ = 13.

在利用輾轉相除法求最大公因數時, 大家不必真的求到 r_n = 0. 例如在上例中可看出 r₀ = 39 和 r₁ = 26 的最大公因數是 13, 利用 Lemma 1.3.1 馬上得知 gcd(a, b) = 13.

在上一節 Corollary 1.2.5 告訴我們若 gcd(a, b) = d, 則存在 m, n $\in$ $\mathbb {Z}$ 使得 d = ma + nb. 當時我們沒有提到如何找到此 m, n. 現在我們利用輾轉相除法來介紹一個找到 m, n 的方法. 我們沿用 Theorem 1.3.2 的符號. 首先看 r₀ = 0 的情形, 此時 d = gcd(a, b) = b 所以若令 m = 0, n = 1, 則我們有 d = b = ma + nb. 當 r₀$\ne$ 0 但 r₁ = 0 時, 我們知 d = gcd(a, b) = r₀. 故利用 a = bh₀ + r₀ 知, 若令 m = 1, n = - h₀, 則 d = r₀ = ma + nb. 同理若 r₀$\ne$ 0, r₁$\ne$ 0 但 r₂ = 0, 則知 d = gcd(a, b) = r₁. 故利用 a = bh₀ + r₀ 以及 b = r₀h₁ + r₁ 知

r₁ = b - r₀h₁ = b - (a - bh₀)h₁ = - h₁a + (1 + h₀h₁)b.

因此若令 m = - h₁ 且 n = 1 + h₀h₁, 則 d = r₁ = ma + nb. 依照此法, 當 r₀, r₁ 和 r₂ 皆不為 0 時, 由於 d = gcd(a, b) = r_{n - 1} 故由 r_{n - 3} = r_{n - 2}h_{n - 1} + r_{n - 1} 知 d = r_{n - 3} - h_{n - 1}r_{n - 2}. 利用前面推導方式我們知存在 m₁, m₂, n₁, n₂ $\in$ $\mathbb {Z}$ 使得 r_{n - 3} = m₁a + n₁b 且 r_{n - 2} = m₂a + n₂b 故代入得

d = (m₁a + n₁b) - h_{n - 1}(m₂a + n₂b) = (m₁ - h_{n - 1}m₂)a + (n₁ - h_{n - 1}n₂)b.

因此若令 m = m₁ - h_{n - 1}m₂ 且 n = n₁ - h_{n - 1}n₂, 則 d = ma + nb.

上面的說明看似好像當 r₀$\ne$ 0 時對每一個 i $\in$ {0, 1,..., n - 2} 要先將 r_i 寫成 r_i = m_ia + n_ib, 最後才可將 d = r_{n - 1} 寫成 ma + nb 的形式. 其實這只是論證時的方便, 在實際操作時我們其實是將每個 r_i 寫成 m_i'r_{i - 2} + n_i'r_{i - 1} 的形式慢慢逆推回 d = ma + nb. 請看以下的例子.

Example 1.3.4   我們試著利用 Example 1.3.3 所得結果找到 m, n $\in$ $\mathbb {Z}$ 使得 13 = gcd(481, 221) = 481m + 221n. 首先我們有 13 = r₂ = 39 - 26 = r₀ - r₁. 而 r₁ = 221 - 5 ^. 39 = b - 5r₀, 故得 13 = r₀ - (b - 5r₀) = 6r₀ - b. 再由 r₀ = 481 - 2 ^. 221 = a - 2b, 得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 會滿足 13 = 481m + 221n.

要注意這裡找到的 m, n 並不會是唯一滿足 d = ma + nb 的一組解. 雖然上面的推演過程好像會只有一組解, 不過只能說是用上面的方法會得到一組解, 並不能擔保可找到所有的解. 比方說若令 m' = m + b, n' = n - a, 則 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m', n' 也會是另一組解. 所以以後當要探討唯一性時, 若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一. 一般的作法是假設你有兩組解, 再利用這兩組解所共同滿足的式子找到兩者之間的關係. 我們看看以下的作法.

Proposition 1.3.5   假設 a, b $\in$ $\mathbb {N}$ 且 d = gcd(a, b). 若 x = m₀, y = n₀ 是 d = ax + by 的一組整數解, 則對任意 t $\in$ $\mathbb {Z}$, x = m₀ + bt/d, y = n₀ - at/d 皆為 d = ax + by 的一組整數解, 而且 d = ax + by 的所有整數解必為 x = m₀ + bt/d, y = n₀ - at/d 其中 t $\in$ $\mathbb {Z}$ 這樣的形式.

証 明. 假設 x = m, y = n 是 d = ax + by 的一組解. 由於已假設 x = m₀, y = n₀ 也是一組解, 故得 am + bn = am₀ + bn₀. 也就是說 a(m - m₀) = b(n₀ - n). 由於 d = gcd(a, b), 我們可以假設 a = a'd, b = b'd 其中 a', b' $\in$ $\mathbb {Z}$ 且 gcd(a', b') = 1 (參見 Corollary 1.2.3). 因此得 a'(m - m₀) = b'(n₀ - n). 利用 b'| a'(m - m₀), gcd(a', b') = 1 以及 Proposition 1.2.7(1) 得 b'| m - m₀. 也就是說存在 t $\in$ $\mathbb {Z}$ 使得 m - m₀ = b't. 故知 m = m₀ + b't = m₀ + bt/d. 將 m = m₀ + bt/d 代回 am + bn = am₀ + bn₀ 可得 n = n₀ - at/d, 因此得證 d = ax + by 的整數解都是 x = m₀ + bt/d, y = n₀ - at/d 其中 t $\in$ $\mathbb {Z}$ 這樣的形式. 最後我們僅要確認對任意 t $\in$ $\mathbb {Z}$, x = m₀ + bt/d, y = n₀ - at/d 皆為 d = ax + by 的一組整數解. 然而將 x = m₀ + bt/d, y = n₀ - at/d 代入 ax + by 得 a(m₀ + bt/d )+ b(n₀ - at/d )= am₀ + bn₀ = d, 故得證本定理. $\qedsymbol$

利用 Proposition 1.3.5 我們就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一組整數解 x = 6, y = - 13 得到 x = 6 + 17t, y = - 13 - 37t 其中 t $\in$ $\mathbb {Z}$ 是 13 = 481x + 221y 所有的整數解.