互質計算器

互質計算器

#1 · 數學和統計 AI Skill PRO

輸入計算

數學公式

互質⇔gcd⁡(a,b)=1\text{互質} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

計算範例

互質⇔gcd⁡(84,126)=1=1\text{互質} \iff \gcd\left(84,\ 126\right) = 1 = 1
使用統計

廣告

結果

84 和 126 互質嗎?
否
gcd(84, 126) = 42
最大公因數 42
互質 否 (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\),兩者互質——即使它們本身都不是質數,也依然成立。

廣告
兩個僅共享公因數 1 的數,以重疊的因數集合表示
當兩個數的唯一公因數是 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 的步驟
歐幾里得演算法逐步縮小這對數,直到餘數顯示 \(\gcd = 1\)。

常見問答

互質的數一定要是質數嗎?不一定。互質的意思只是兩數沒有大於 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)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (因為 \(47 \times 21 = 987\) 且 \(1024 - 987 = 37\))
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(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)

  1. \(84 \bmod 126 = 84\),所以第一步簡單地將配對交換為 \((126,\ 84)\)
  2. \(126 \bmod 84 = 42\)
  3. \(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)

  1. \(54 \bmod 25 = 4\)  (因為 \(25 \times 2 = 50\) 且 \(54 - 50 = 4\))
  2. \(25 \bmod 4 = 1\)  (因為 \(4 \times 6 = 24\) 且 \(25 - 24 = 1\))
  3. \(4 \bmod 1 = 0\) → 停止

最後非零的餘數是 \(1\),所以 \(\gcd(25, 54) = 1\)。判決:25 和 54 互質。 此處 \(25 = 5^2\) 且 \(54 = 2 \times 3^3\);質集合 \(\{5\}\) 和 \(\{2, 3\}\) 不相交。這是互質性的關鍵點:它是一個配對的性質,不是個別數字的性質 — 沒有任何數字必須是質數。

計算慣例與邊界情況

以下每個情況都在本計算機上實際執行過,結果欄就是它真正回傳的值。

情況輸入結果
1 和 91, 9是
0 和 50, 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|\)。
最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器