最大公因數計算機

輸入計算

第一個數 (a)

第二個數 (b)

結果

最大公因數

12

GCF of 48 and 36

最大公因數 (GCF)	12
最小公倍數 (LCM)	144

什麼是最大公因數？

最大公因數（GCF），又稱最大公約數（GCD）或最高公因數（HCF），指的是能同時整除兩個整數、且不留餘數的最大正整數。舉例來說，48 和 36 的最大公因數是 12，因為 12 是同時能整除這兩個數的最大數值。本計算機可即時算出最大公因數，並一併顯示最小公倍數（LCM）。

最大公因數是兩個數共有質因數的乘積。

如何使用本計算機

在標示為 a 和 b 的欄位中分別輸入兩個非負整數，接著送出即可。工具會回傳最大公因數，以及最小公倍數。輸入順序不影響結果——\(\text{GCF}(48, 36)\) 與 \(\text{GCF}(36, 48)\) 完全相同。

公式原理說明

本計算機採用輾轉相除法（歐幾里得演算法），這是一套源自古希臘的優雅方法。其原理在於：兩數的最大公因數也必能整除它們相除後的餘數。具體做法是反覆將數對 \((a, b)\) 替換為 \((b, a \bmod b)\)，直到第二個數變為 0 為止，此時剩下的第一個數即為最大公因數。最小公倍數則可用公式求得。

$$\text{lcm}(a, b) = \frac{a \times b}{\text{gcf}(a, b)}$$

歐幾里得演算法反覆將 \((a, b)\) 替換為 \((b, a \bmod b)\)，直到 \(b\) 變為 0。

實際範例

以求 48 和 36 的最大公因數為例。步驟一：\(48 \bmod 36 = 12\)，數對變為 \((36, 12)\)。步驟二：\(36 \bmod 12 = 0\)，數對變為 \((12, 0)\)。由於第二個值為 0，最大公因數即為 12。最小公倍數則為 $$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$

常見問題

若其中一個數為 0，最大公因數是多少？依定義，\(\text{GCF}(a, 0) = a\)。而 0 和 0 的最大公因數為 0。

GCF 和 HCF 是同一回事嗎？是的。GCF、GCD 和 HCF 只是同一個數值的不同名稱。

當兩個數沒有共同因數時，最大公因數是多少？答案是 1，此時這兩個數稱為互質（coprime，又稱互素）。