互質計算器

輸入計算

第一個數 (a)

第二個數 (b)

結果

Are 12 and 35 relatively prime?

Yes

gcd(12, 35) = 1

最大公因數	1
互質	Yes (gcd = 1)

什麼是互質計算器？

當兩個整數唯一的共同正因數只有 1 時，我們稱這兩數互質（英文為 coprime 或 relatively prime）。換句話說，它們的最大公因數（gcd）恰好等於 1。這個計算器讓你輸入兩個整數，便能立刻得知它們是否互質，並同時顯示兩數的最大公因數。

如何使用

分別在 a 與 b 兩個欄位輸入整數後送出，工具會以「輾轉相除法」（歐幾里得演算法）計算 \(\gcd(a, b)\)。若最大公因數為 1，代表兩數互質；若大於 1，則表示兩數有共同因數，並不互質。由於互質與否只看絕對值，因此負號會被自動忽略。

公式說明

輾轉相除法會不斷將數對 \((a, b)\) 換成 \((b, a \bmod b)\)，直到第二個數變為 0 為止；最後一個非零的數值就是最大公因數。當這個 gcd 等於 1 時，兩數即為互質。

$$\text{Coprime} \iff \gcd\left(a,\ b\right) = 1$$

舉例來說，8 與 15 沒有任何共同的質因數，所以 \(\gcd = 1\)，兩者互質——即使它們本身都不是質數，也依然成立。

Advertisement

當兩個數的唯一公因數是 1 時它們互質，因此 \(\gcd(a, b) = 1\)。

實際範例

以 \(a = 12\)、\(b = 35\) 為例。12 的質因數為 2 與 3；35 的質因數為 5 與 7。兩者沒有任何共同的質因數，因此 \(\gcd(12, 35) = 1\)，所以 12 與 35 互質。相對地，12 與 18 同時擁有因數 6，\(\gcd = 6\)，兩者就不互質。

歐幾里得演算法逐步縮小這對數，直到餘數顯示 \(\gcd = 1\)。

常見問答

互質的數一定要是質數嗎？不一定。互質的意思只是兩數沒有大於 1 的共同因數，數字本身不必是質數（例如 8 與 9 互質）。

1 與任何數都互質嗎？是的。對任意整數 n 而言，\(\gcd(1, n) = 1\)，所以 1 與每一個整數都互質。

兩個偶數有可能互質嗎？不可能。任何兩個偶數都共有因數 2，因此它們的最大公因數至少是 2。