gcd 終止、正確性與程式

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

1. 步驟（遞迴定義）

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

要是 \(m \lt n\)，計算 \(gcd \; n \; m\)
求 \(m / n\) 的餘數，也就是 \(m = q \cdot n + r\)
要是 \(r = 0\)，回傳 \(n\)
計算 \(gcd \; n \; r\)

2. 終止性

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

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

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

3. 正確性

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

首先回溯定義初始 \(r_0 = m\)，\(r_1 = n\)，與接著所有的 \(r\) 構成一個有限序列 \(r_k\)。

根據終止性最後一個餘數必定是 \(r_N = 0\)，\(N\) 表示滿足終止條件時的最後一個 \(r\) 在 \(r_k\) 上的標簇。

定義 \(g\) 是 \(m\)、\(n\) 的最大公因數

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

首先，我們知道 \(r_{k-2} = q\cdot r_{k−1} + r_k\)
根據這是演算法的終止條件，可以知道 \(r_{N-2} = q\cdot r_{N−1} + 0 = q\cdot r_{N−1}\)，這可以得出 \(r_{N-1}\) 是 \(r_{N-2}\) 的因數的結論
再次使用餘數關係，可以知道 \(r_{N-3} = q\cdot r_{N−2} + r_{N-1}\)
而因為 \(r_{N-1}\) 可以整除 \(r_{N-2}\) 所以也可以整除 \(r_{N-3}\)
再次利用等式 \(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