互いに素の判定計算機とは?
2つの整数が互いに素(英語でcoprime、コプライムとも呼ばれます)であるとは、両方を割り切る正の整数が1しかない状態を指します。言い換えれば、最大公約数(gcd)がちょうど1になるということです。この計算機に2つの整数を入力すると、それらが互いに素かどうかを、最大公約数とあわせて瞬時に判定します。
使い方
a と b の入力欄にそれぞれ整数を入れて実行するだけです。ツールはユークリッドの互除法を使って \(\gcd(a, b)\) を計算します。最大公約数が1なら2つの数は互いに素であり、1以外であれば共通の約数を持つため互いに素ではありません。互いに素かどうかは絶対値だけで決まるため、マイナスの符号は無視して計算します。
計算式の仕組み
ユークリッドの互除法では、ペア \((a, b)\) を \((b, a \bmod b)\) に置き換える操作を、2番目の値が0になるまで繰り返します。このとき最後に残った0でない値が最大公約数です。そして、この最大公約数が1のときに限り、2つの数は互いに素になります。
$$\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\) となり、互いに素ではありません。
さらに互いに素な例
ユークリッドの互除法は、余りが0になるまで、対\((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\) → 停止
最後の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\) → 停止
最後の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\)です。より小さい数を最初に配置すると1つの余分な交換ステップだけが必要になることに注意してください — アルゴリズムは順序付けられた入力を必要としません。
例3 — 互いに素である2つの合成数: 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\) → 停止
最後の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\)の中で一意な解を持ちます。これはベズーの等式に従い、$$a x + b y = 1$$を満たす整数\(x, y\)を保証します。その式を\(b\)を法として約分すると\(a x \equiv 1\)が残ります。\(a = 25\)、\(b = 54\)の場合: \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\)であるため、54を法とした25の逆元は13です。
- lcmは単純な積です: \(\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\)は完全な周期を生成します。gcdが\(d > 1\)であれば、歩行は\(b/d\)個の\(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\)個の解を持ちます。
- lcmは積より小さいです: \(\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および1を含む)と互いに素です: \(\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(1071, 1024) = 1\)と同様に\(\gcd(-25, 54) = 1\)です。
- 数が自分自身と互いに素であるのは\(|a| = 1\)のときのみです。\(\gcd(a,a) = |a|\)だからです。
計算の約束事と境界ケース
以下の各ケースは実際にこの計算ツールで計算したもので、結果欄はツールが返す値そのものです。
| ケース | 入力 | 結果 |
|---|---|---|
| 1 と 9 | 1, 9 | はい |
| 0 と 5 | 0, 5 | いいえ |
2026-11-08に確認
よくある質問(FAQ)
互いに素な数は素数でなければならないのですか? いいえ。互いに素とは「1より大きい共通の約数を持たない」という意味であり、数そのものが素数である必要はありません(例:8と9)。
1はすべての数と互いに素ですか? はい。任意の整数 n に対して \(\gcd(1, n) = 1\) となるため、1はあらゆる整数と互いに素です。
2つの偶数が互いに素になることはありますか? いいえ。どんな2つの偶数も約数2を共有するので、最大公約数は必ず2以上になります。