什麼是互質計算器?
當兩個整數唯一的共同正因數只有 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\),兩者互質——即使它們本身都不是質數,也依然成立。
實際範例
以 \(a = 12\)、\(b = 35\) 為例。12 的質因數為 2 與 3;35 的質因數為 5 與 7。兩者沒有任何共同的質因數,因此 \(\gcd(12, 35) = 1\),所以 12 與 35 互質。相對地,12 與 18 同時擁有因數 6,\(\gcd = 6\),兩者就不互質。
常見問答
互質的數一定要是質數嗎?不一定。互質的意思只是兩數沒有大於 1 的共同因數,數字本身不必是質數(例如 8 與 9 互質)。
1 與任何數都互質嗎?是的。對任意整數 n 而言,\(\gcd(1, n) = 1\),所以 1 與每一個整數都互質。
兩個偶數有可能互質嗎?不可能。任何兩個偶數都共有因數 2,因此它們的最大公因數至少是 2。
更多互質的例子
歐幾里得演算法反覆地用 \((b,\ a \bmod b)\) 取代配對 \((a,\ b)\),直到餘數為 \(0\)。最後非零的餘數是 \(\gcd(a,b)\),而配對互質當且僅當該值為 \(1\)。
例 1 — 一個較大的互質配對:gcd(1071, 1024)
- \(1071 \bmod 1024 = 47\)
- \(1024 \bmod 47 = 37\) (因為 \(47 \times 21 = 987\) 且 \(1024 - 987 = 37\))
- \(47 \bmod 37 = 10\)
- \(37 \bmod 10 = 7\)
- \(10 \bmod 7 = 3\)
- \(7 \bmod 3 = 1\)
- \(3 \bmod 1 = 0\) → 停止
最後非零的餘數是 \(1\),所以 \(\gcd(1071, 1024) = \) 1。判決:1071 和 1024 互質(互質) — 即使兩者都不是質數(\(1071 = 3 \times 3 \times 7 \times 17\) 且 \(1024 = 2^{10}\)),它們不共享任何質因數。
例 2 — 一個非互質的配對:gcd(84, 126)
- \(84 \bmod 126 = 84\),所以第一步簡單地將配對交換為 \((126,\ 84)\)
- \(126 \bmod 84 = 42\)
- \(84 \bmod 42 = 0\) → 停止
最後非零的餘數是 \(42\),所以 \(\gcd(84, 126) = \) 42。判決:84 和 126 不互質。 因式分解確認:\(84 = 2^2 \times 3 \times 7\) 且 \(126 = 2 \times 3^2 \times 7\),所以共用部分是 \(2 \times 3 \times 7 = 42\)。注意將較小的數字放在前面只需額外增加一個交換步驟 — 該演算法不要求有序輸入。
例 3 — 兩個仍然互質的合數:gcd(25, 54)
- \(54 \bmod 25 = 4\) (因為 \(25 \times 2 = 50\) 且 \(54 - 50 = 4\))
- \(25 \bmod 4 = 1\) (因為 \(4 \times 6 = 24\) 且 \(25 - 24 = 1\))
- \(4 \bmod 1 = 0\) → 停止
最後非零的餘數是 \(1\),所以 \(\gcd(25, 54) = 1\)。判決:25 和 54 互質。 此處 \(25 = 5^2\) 且 \(54 = 2 \times 3^3\);質集合 \(\{5\}\) 和 \(\{2, 3\}\) 不相交。這是互質性的關鍵點:它是一個配對的性質,不是個別數字的性質 — 沒有任何數字必須是質數。
計算慣例與邊界情況
以下每個情況都在本計算機上實際執行過,結果欄就是它真正回傳的值。
| 情況 | 輸入 | 結果 |
|---|---|---|
| 1 和 9 | 1, 9 | 是 |
| 0 和 5 | 0, 5 | 否 |
核對於 2026-11-08
你的結果代表什麼
計算機報告單一數字 \(d = \gcd(a,b)\),而判決取決於 \(d\) 是否等於 \(1\)。每個分支都帶有一組特定的標準數論結果。
如果 gcd(a, b) = 1 — 數字互質
- 分數 \(a/b\) 已經是最簡形式。 沒有大於 \(1\) 的整數可以從分子和分母中約分。
- \(a\) 在模 \(b\) 下有乘法逆元(且 \(b\) 在模 \(a\) 下也有):同餘方程 \(a \cdot x \equiv 1 \pmod b\) 可解,在剩餘 \(0, 1, \ldots, b-1\) 中有唯一解。這來自於貝祖等式,它保證存在整數 \(x, y\) 使得 $$a x + b y = 1$$ 將該方程模 \(b\) 化簡後得到 \(a x \equiv 1\)。對於 \(a = 25\)、\(b = 54\):\(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\),所以 \(25\) 在模 \(54\) 下的逆元是 \(13\)。
- 最小公倍數就是純乘積: \(\operatorname{lcm}(a,b) = a \cdot b\)。對於 \(25\) 和 \(54\),\(\operatorname{lcm} = 25 \times 54 = 1350\)。
- 中國剩餘定理適用於模數 \(a\) 和 \(b\)。 任何系統 \(x \equiv r \pmod a\)、\(x \equiv s \pmod b\) 都有解,在模 \(a \cdot b\) 下唯一 — 例如對於模數 \(25\) 和 \(54\),在模 \(1350\) 下唯一。
- 在長度 \(b\) 的循環中以 \(a\) 為步長訪問每個位置。 乘倍 \(0, a, 2a, 3a, \ldots\) 模 \(b\) 化簡後會通過所有 \(b\) 個剩餘類,然後重複;\(a\) 產生完整的循環。如果最大公約數是 \(d > 1\),該遍歷只會接觸被 \(d\) 整除的 \(b/d\) 個位置。
- 等價地,\(a\) 和 \(b\) 的質因數分解不共享任何質數,且 \(a\) 被歐拉拓展函數 \(\varphi(b)\) 計算。
如果 gcd(a, b) = d > 1 — 數字不互質
- 分數 \(a/b\) 可以約分。 將兩部分都除以 \(d\) 得到 \((a/d)\,/\,(b/d)\),且該配對互質,所以約分後的分數是最簡形式。對於 \(a = 84\)、\(b = 126\)、\(d = 42\):\(84/126 = 2/3\),且 \(\gcd(2,3) = 1\)。
- \(a\) 在模 \(b\) 下的乘法逆元不存在。 同餘方程 \(a \cdot x \equiv 1 \pmod b\) 沒有解,因為每個 \(a x - 1\) 是 \(b\) 的倍數的值都會迫使 \(d \mid 1\)。更一般地,\(a x \equiv c \pmod b\) 只有在 \(d \mid c\) 時才可解,且此時它在模 \(b\) 下恰好有 \(d\) 個解。
- 最小公倍數小於乘積: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\)。對於 \(84\) 和 \(126\):\(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\)。
- 貝祖等式仍然成立,但形式為 \(a x + b y = d\) — \(a x + b y\) 能取的最小正值是 \(d\),永遠不是 \(1\)。中國剩餘定理的基本形式不適用於模數 \(a\) 和 \(b\)。
邊界情況
- 對每個整數 \(n\),\(\gcd(1, n) = 1\),所以 \(1\) 與所有數都互質,包括 \(0\) 和它本身:\(\gcd(1,1) = 1\)。
- \(\gcd(0, n) = |n|\),因為每個整數都整除 \(0\)。因此 \(0\) 只與 \(1\) 和 \(-1\) 互質。
- \(\gcd(0, 0)\) 沒有最大公約數 — 每個整數都整除 \(0\),所以公約數集合是無界的。按慣例定義為 \(0\),且配對 \((0,0)\) 不互質。
- 符號不相關:\(\gcd(a,b) = \gcd(|a|, |b|)\),所以 \(\gcd(-25, 54) = 1\) 就像 \(\gcd(25, 54) = 1\) 一樣。
- 一個數與自身互質當且僅當 \(|a| = 1\),因為 \(\gcd(a,a) = |a|\)。