最大公因數與最小公倍數計算機

最後更新：2026-05-13

兩整數之間的兩種基本關係

任意一對正整數都有兩個特殊的數：能同時整除兩者的最大正整數（最大公因數，GCD〔Greatest Common Divisor〕），以及同時為兩者倍數的最小正整數（最小公倍數，LCM〔Least Common Multiple〕）。這兩個數合在一起，刻畫了兩個整數之間的算術關係。

以 12 和 8 為例：

• 12 和 8 的公因數為 1、2、4，其中最大的是 4。
• 12 和 8 的公倍數為 24、48、72……，其中最小的是 24。

歐幾里得算法求最大公因數

求最大公因數最古老——在實務上也仍是最快——的方法是歐幾里得算法，約於西元前 300 年由歐幾里得在《幾何原本》中描述。其核心性質如下：

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

其中 $a \bmod b$ 是 $a$ 除以 $b$ 的餘數。反覆進行直到餘數為零，最後一個非零餘數即為最大公因數。

範例：GCD(48, 18)

步驟	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

最後一個非零餘數為 6，故 GCD(48, 18) = 6。

此算法的步驟數永遠不超過較小那個數位數的五倍，即使對大數也保持高效。

最大公因數與最小公倍數的恆等式

一旦求得最大公因數，只需一個公式即可得到最小公倍數：

$\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

這並非巧合，而是由整數唯一質因數分解定理推導出的定理。若把每個整數視為質數冪次的乘積，最大公因數取每個質數的最小次方，最小公倍數取最大次方，兩者之積恆等於 $a \times b$。

範例：LCM(12, 8)

$\text{GCD}(12, 8) = 4, \quad \text{LCM}(12, 8) = \frac{12 \times 8}{4} = 24$

驗算：$4 \times 24 = 96 = 12 \times 8$，等式成立。

主要應用

化簡分數

將 $\dfrac{a}{b}$ 化為最簡分數，只需將分子與分母同除以 $\gcd(a, b)$。例如 $\dfrac{12}{8}$ 化簡為 $\dfrac{3}{2}$，因為 $\gcd(12, 8) = 4$。

分數加法

計算 $\dfrac{1}{12} + \dfrac{1}{8}$ 時，需要最小公分母，即 $\text{LCM}(12, 8) = 24$：

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

週期與循環問題

若兩件事分別每 $a$ 天和每 $b$ 天重複一次，則下次同時發生在 $\text{LCM}(a, b)$ 天後。因此齒輪傳動比、磁磚紋樣的週期，以及曆法問題（兩個天象週期何時再次重合？）中都會出現最小公倍數。

密碼學

歐幾里得算法是 RSA 加密的核心基本運算，GCD 用於驗證所選的金鑰指數是否與模數的歐拉函數互質。

特殊情況

• GCD(a, 0) = a（$a$ 為任意正整數）：這是歐幾里得算法的基底情況，直接由定義推導而來。
• 互質的數：最大公因數 = 1，最小公倍數 = a × b。例如 GCD(7, 13) = 1，LCM(7, 13) = 91。
• 相等的數：GCD(n, n) = n，LCM(n, n) = n。

快速參考

性質	公式
歐幾里得算法	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
由最大公因數求最小公倍數	$\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$
恆等式	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$
化簡分數	分子分母同除以 $\gcd$
公分母	取兩分母的 $\text{lcm}$

常見問題（FAQ）

什麼是最大公因數？

最大公因數（GCD）是能同時整除兩個整數的最大正整數。例如，GCD(12, 8) = 4，因為 4 是能同時整除 12 和 8 且不留餘數的最大數。

什麼是最小公倍數？

最小公倍數（LCM）是同時為兩個整數之倍數的最小正整數。例如，LCM(12, 8) = 24，因為 24 是同時為 12 和 8 之倍數的最小數。

最大公因數和最小公倍數有什麼關係？

對任意兩個正整數 a 與 b，恆有 GCD(a, b) × LCM(a, b) = a × b。這表示可以由其中一個推算另一個：LCM = a × b ÷ GCD。正是這層關係，使得這兩個值通常一起計算。