UP | HOME

gcd 終止、正確性與程式

gcd 函數接收兩個參數 \(m\) 跟 \(n\),用來尋找兩正整數之間的最大公因數。

1. 步驟(遞迴定義)

\(gcd \; m \; n\) 定義為

  1. 要是 \(m \lt n\),計算 \(gcd \; n \; m\)
  2. 求 \(m / n\) 的餘數,也就是 \(m = q \cdot n + r\)
  3. 要是 \(r = 0\),回傳 \(n\)
  4. 計算 \(gcd \; n \; r\)

2. 終止性

首先,不管 \(m\) 是什麼,下述都成立。因為餘式定理,知道 \(0 \le r \lt n\)

  1. \(n\) 在整個演算法中每步都在減少,也就是說 \(r\) 也跟著每步都在縮小(根據 \(r \lt n\))
  2. \(r\) 有非負這個特性(根據 \(0 \le r\))

可以知道 \(r\) 會在有限步之後為 \(0\),也就證明程式會終止。

3. 正確性

要證明正確性,可以分成兩個部分。

  1. 首先回溯定義初始 \(r_0 = m\),\(r_1 = n\),與接著所有的 \(r\) 構成一個有限序列 \(r_k\)。
  2. 根據終止性最後一個餘數必定是 \(r_N = 0\),\(N\) 表示滿足終止條件時的最後一個 \(r\) 在 \(r_k\) 上的標簇。
  3. 定義 \(g\) 是 \(m\)、\(n\) 的最大公因數

3.1. 第一部分,證明最終結果 \(r_{N−1}\) 是 \(m\) 和 \(n\) 的公因數

  1. 首先,我們知道 \(r_{k-2} = q\cdot r_{k−1} + r_k\)
  2. 根據這是演算法的終止條件,可以知道 \(r_{N-2} = q\cdot r_{N−1} + 0 = q\cdot r_{N−1}\),這可以得出 \(r_{N-1}\) 是 \(r_{N-2}\) 的因數的結論
  3. 再次使用餘數關係,可以知道 \(r_{N-3} = q\cdot r_{N−2} + r_{N-1}\)
  4. 而因為 \(r_{N-1}\) 可以整除 \(r_{N-2}\) 所以也可以整除 \(r_{N-3}\)
  5. 再次利用等式 \(r_{k-2} = q\cdot r_{k−1} + r_k\),就可以知道 \(r_{N-1}\) 整除任意 \(r_k\),除了 \(r_N = 0\)。而 \(m\)、\(n\) 本來就屬於 \(r_k\),所以 \(r_{N−1}\) 確實是 \(m\)、\(n\) 的公因數

3.2. 第二部分,證明 \(g\) 整除 \(r_{N−1}\)

根據定義 \(g\) 整除 \(m\)、\(n\),所以我們可以把 \(m\)、\(n\) 改寫成

  • \(m = r_0 = p \cdot g\)
  • \(n = r_1 = q \cdot g\)

於是從

\begin{aligned} r_2 &= r_0 - v \cdot r_1 \\&= p \cdot g - v \cdot r_1 \\&= p \cdot g - v \cdot q \cdot g \\&= (p - v \cdot q) \cdot g \end{aligned}

可以看出 \(g\) 整除 \(r_2\),且只要有 \(g\) 可以整除 \(r_{k-2}\) 跟 \(r_{k-1}\),這個論述可以推廣到任何 \(2 \le k \le N-1\) 的 \(r_k\)。所以 \(g\) 也整除 \(r_{N-1}\)

3.3. 得證

從第一部分知道,因為 \(r_{N−1}\) 是 \(m\) 和 \(n\) 的公因數,所以小於等於最大公因數。也就是 \(r_{N−1} \le g\)。

從第二部分知道 \(g \le r_{N−1}\)。

結合兩個不等式就知道 \(r_{N−1} = g\)。

4. 程式

最後就用程式總結,說了這麼多到底在幹嘛

gcd : Int -> Int -> Int
gcd m n =
  let m = m `mod` n
  in if m == 0 then n else n `gcd` m
Date: 2022-12-09 Fri 00:00
Author: Lîm Tsú-thuàn