液晶顯示模組
計算多個數的 GCD 和 LCM
如何使用液晶顯示模組
- 1輸入兩個或多個整數。
- 2執行計算器求最大公約數。
- 3檢視最大公約數，以及（如需）歐幾里得演算法的步驟。
最大公約數
gcd(a,b) = gcd(b, a mod b)，直到餘數為 0；最後一個非零餘數即最大公約數最大公約數是能無餘數整除每個輸入的最大整數，用於把分數約到最簡。
歐幾里得演算法不斷用餘數替換較大數，比逐個試除快得多。
輾轉相除法的核心洞察是：gcd(a, b) = gcd(b, a mod b)。也就是說，兩個數的最大公約數，等於較小數與餘數的最大公約數。反覆應用這個關係直到餘數為 0，最後的除數就是答案。它的效率極高——即使對幾百位的數，計算次數也只是位數的小倍數，這是它歷經兩千多年仍在使用的原因。
最大公約數的實用場景比想像中多：約分分數（分子分母同除 GCD 直接得到最簡形式）、鋪磚問題（用最大尺寸的正方形磚鋪滿矩形地面，磚邊長就是長寬的 GCD）、以及密碼學（RSA 演算法需要計算模逆元，用擴充套件歐幾里得演算法）。兩個數 GCD 為 1 時稱「互質」，這在分數運算和密碼學中都有特殊意義。
| 數對 | 計算過程 | GCD | 說明 |
|---|---|---|---|
| 12, 18 | 18 = 12×1 + 6 → 12 = 6×2 + 0 | 6 | 餘數為 0 時的除數 |
| 48, 18 | 48 = 18×2 + 12 → 18 = 12×1 + 6 → 12 = 6×2 + 0 | 6 | 三步得出 |
| 100, 75 | 100 = 75×1 + 25 → 75 = 25×3 + 0 | 25 | 兩步得出 |
| 17, 5 | 17 = 5×3 + 2 → 5 = 2×2 + 1 → 2 = 1×2 + 0 | 1 | 互質 |
用輾轉相除法（歐幾里得演算法）求最大公約數
常見問題
最大公約數有什麼用？
約分，以及作為求最小公倍數與模運算的一步。
負數有最大公約數嗎？
有，最大公約數取絕對值，符號不影響結果。
若兩數無公因數？
則最大公約數為 1，兩數稱為互質。
為什麼叫「輾轉相除」？
「輾轉」是反覆、輪流的意思，形象地描述了演算法過程：用大數除以小數，再用上一輪的除數和餘數繼續相除，一輪輪「輾轉」下去直到餘數為零。這個方法記載於歐幾里得《幾何原本》（約西元前 300 年），是人類歷史上最早記載的演算法之一，比很多後來的數學發現早了一千多年。
三個數的最大公約數怎麼求？
利用結合律：gcd(a, b, c) = gcd(gcd(a, b), c)。先求前兩個數的 GCD，再用這個結果與第三個數求 GCD，可以推廣到任意多個數。例如求 gcd(12, 18, 30)：先算 gcd(12, 18) = 6，再算 gcd(6, 30) = 6，答案是 6。同理，多個數的最小公倍數也可以用 lcm(a, b, c) = lcm(lcm(a, b), c) 遞推。