GCD 和 LCM 是什麼？
最大公因數（GCD）和最小公倍數（LCM）是數論中最基礎也最實用的概念，從國小數學到密碼學都會用到。
- GCD（Greatest Common Divisor）：能同時整除兩個數的最大正整數
- LCM（Least Common Multiple）：能同時被兩個數整除的最小正整數
例如，12 和 18：
- 12 的因數：1, 2, 3, 4, 6, 12
- 18 的因數：1, 2, 3, 6, 9, 18
- 公因數：1, 2, 3, 6 → GCD = 6
- LCM = 36（最小的同時被 12 和 18 整除的數）
輾轉相除法（歐幾里得演算法）
這是計算 GCD 最高效的方法，由古希臘數學家歐幾里得在西元前 300 年提出，是已知最古老的演算法之一。
演算法步驟
- 將較大數除以較小數，記下餘數
- 用除數取代被除數，用餘數取代除數
- 重複步驟 1-2，直到餘數為 0
- 最後的除數就是 GCD
計算範例
以 GCD(48, 18) 為例：
| 步驟 | 運算 | 餘數 |
|---|---|---|
| 1 | 48 = 18 x 2 + 12 | 12 |
| 2 | 18 = 12 x 1 + 6 | 6 |
| 3 | 12 = 6 x 2 + 0 | 0 |
餘數為 0 時停止，最後的除數 6 就是 GCD(48, 18)。
用 GCD 求 LCM
LCM(A, B) = A x B / GCD(A, B)
LCM(48, 18) = 48 x 18 / 6 = 144
這個公式利用了 GCD 和 LCM 的乘積關係，避免了直接尋找公倍數的低效方式。
GCD 和 LCM 的重要性質
| 性質 | 公式 |
|---|---|
| 乘積關係 | GCD(A,B) x LCM(A,B) = A x B |
| 互質條件 | GCD(A,B) = 1 時，A 和 B 互質 |
| 整除關係 | GCD(A,B) 一定整除 A 和 B |
| 自身性質 | GCD(A,A) = A，LCM(A,A) = A |
| 與 1 的關係 | GCD(A,1) = 1，LCM(A,1) = A |
生活中的應用
分數化簡
將 48/18 化為最簡分數： GCD(48, 18) = 6，所以 48/18 = (48/6)/(18/6) = 8/3
分數通分
計算 1/4 + 1/6： LCM(4, 6) = 12，所以 1/4 + 1/6 = 3/12 + 2/12 = 5/12
週期同步
紅色燈每 4 秒閃一次，綠色燈每 6 秒閃一次。何時會同時閃爍？ LCM(4, 6) = 12，所以每 12 秒兩燈同時閃爍一次。
分配問題
要把 48 個蘋果和 36 個橘子平均分給最多的人，每人分到同樣多的蘋果和橘子： GCD(48, 36) = 12，最多可以分給 12 人，每人 4 個蘋果和 3 個橘子。
互質的概念
當兩個數的 GCD 等於 1 時，稱它們為互質（Coprime）。互質不代表兩個數都是質數，只代表它們不共用任何質因數。
互質的重要性
- LCM 就等於兩數的乘積（因為 GCD = 1）
- 在 RSA 加密演算法中，選取兩個互質的大數是安全性的基礎
- 連續整數必定互質：GCD(n, n+1) = 1
常見的互質數對
- (2, 3)、(3, 5)、(7, 11) — 任意兩個不同質數
- (8, 15)、(9, 14)、(16, 25) — 不共用質因數的合數
延伸：多個數的 GCD 和 LCM
三個以上的數也可以計算 GCD 和 LCM，方法是逐步套用兩數的計算：
- GCD(A, B, C) = GCD(GCD(A, B), C)
- LCM(A, B, C) = LCM(LCM(A, B), C)
例如 GCD(12, 18, 24) = GCD(GCD(12,18), 24) = GCD(6, 24) = 6
本計算機使用歐幾里得演算法，時間複雜度為 O(log(min(A,B)))，即使輸入大數也能瞬間計算出結果。同時顯示完整的計算步驟，方便學習理解。