什么是互质数计算器?
当两个整数只有 1 这一个共同的正因数时,我们称它们互质(也叫互素)。换句话说,它们的最大公约数(gcd)恰好等于 1。本计算器只需输入两个整数,即可立刻告诉你它们是否互质,并给出对应的最大公约数。
如何使用
在 a 和 b 两个输入框中分别填入你的整数,然后提交。工具会用欧几里得算法(辗转相除法)计算 \(\gcd(a,\ b)\)。如果结果为 1,说明两数互质;如果大于 1,则它们存在公因数,并不互质。由于互质只取决于绝对值,负号会被自动忽略。
公式解析
欧几里得算法的做法是:不断把数对 \((a,\ b)\) 替换为 \((b,\ a \bmod b)\),直到第二个数变成 0 为止。此时最后一个非零的值就是最大公约数。当这个 gcd 恰好等于 1 时,两数即为互质。
$$\text{Coprime} \iff \gcd\left(\text{a},\ \text{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\),因此它们并不互质。
更多互质数例子
欧几里得算法反复地将数对 \((a,\ b)\) 替换为 \((b,\ a \bmod 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\}\) 是不相交的。这是关于互质性的关键点:它是一对数的性质,而不是各个数的性质——两个数都不必是质数。
您的结果意味着什么
计算器报告单个数字 \(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\) 下唯一。
- 以 \(a\) 步长绕长度为 \(b\) 的循环访问每个位置。倍数 \(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\) 时可解,且恰好有 \(d\) 个解在模 \(b\) 下。
- 最小公倍数小于乘积:\(\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\)。
边界情况
- \(\gcd(1, n) = 1\) 对于每个整数 \(n\),所以\(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|\)。
计算约定与边界情况
以下每个情况都在本计算器上实际运行过,结果一栏就是它真实返回的值。
| 情况 | 输入 | 结果 |
|---|---|---|
| 1 和 9 | 1, 9 | 是 |
| 0 和 5 | 0, 5 | 否 |
核对于 2026-11-08
常见问题
互质的数一定都是质数吗?不是。互质指的是它们没有大于 1 的公因数,这两个数本身并不需要是质数(例如 8 和 9)。
1 和任何数都互质吗?是的。对任意整数 \(n\),都有 \(\gcd(1,\ n) = 1\),所以 1 与每一个整数都互质。
两个偶数有可能互质吗?不可能。任意两个偶数都含有公因数 2,所以它们的 gcd 至少是 2。