乗法逆元とは?
ある数の乗法逆元とは、その数に掛け合わせると 1 になる値のことです。普通の実数 \(a\) の場合、逆元は単純にその逆数 \(1/a\) になります。たとえば 4 の逆元は 0.25 です。\(4 \times 0.25 = 1\) となるためです。なお、0 に逆元は存在しません。どんな数を 0 に掛けても 1 にはならないからです。
モジュラ逆数(合同式の逆元)
合同算術(モジュラ計算)における \(a\) の乗法逆元(mod \(m\))とは、$$\text{Number (a)} \cdot a^{-1} \equiv 1 \pmod{\text{Modulus (m)}}$$ を満たす 0 から \(m-1\) の範囲の整数 \(x\) のことです。これは整数論や暗号理論(RSA、ハッシュ、誤り訂正符号など)で頻繁に登場します。モジュラ逆数が存在するのは、\(a\) と \(m\) が互いに素なとき、つまり \(\gcd(a, m) = 1\) のときに限られます。この計算機は拡張ユークリッドの互除法を用いて逆元を求めます。
この計算機の使い方
まず数 \(a\) を入力します。法(modulus)を 0 のまま(または空欄)にすると、通常の逆数 \(1/a\) が求められます。モジュラ逆数を計算したい場合は、1 より大きい法 \(m\) を入力してください。計算機は \(a\) を \(m\) で割った余りに変換したうえで逆元を返します。\(a\) と \(m\) に共通の約数がある場合は、逆元が存在しないことを表示します。
計算例
3 の mod 11 における逆元を求めてみましょう。\(3x \equiv 1 \pmod{11}\) を満たす \(x\) が必要です。\(x = 4\) を試すと $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}$$ となります。したがってモジュラ逆数は 4 です。一方、逆数としての 3 の逆元は \(1/3 \approx 0.333333\) になります。
拡張ユークリッドの互除法で手計算する剰余逆元
法 \(m\) における \(a\) の剰余逆元とは、\(a \cdot x \equiv 1 \pmod{m}\) を満たす数 \(x\) のことです。これは \(\gcd(a, m) = 1\) のときに限って存在します。拡張ユークリッドの互除法を使えば、この \(x\) を求めることができます。
- ユークリッドの互除法を実行する。\((m, a)\) の組に対して繰り返し割り算を行い、組 \((m, a)\) を \((a, r)\) に置き換えます。ここで \(r\) は余りです。余りが 0 になるまで続けます。
- 最大公約数を確認する。最後の非ゼロの余りが \(\gcd(a, m)\) です。これが 1 でなければ逆元は存在しないので、ここで終了します。
- 割り算の各行を逆にたどって代入する(後退代入)。\(1 = a \cdot x + m \cdot y\) の形に書き直します。
- \(x\) を法 \(m\) で 0 から \(m-1\) の範囲に収める。\(x\) が負の場合は \(m\) を加えます。
- 検算する。\(a \cdot x \bmod m = 1\) となることを確かめます。
例:法 26 における 7 の剰余逆元。
| 行 | 割り算 | 商 | 余り |
|---|---|---|---|
| 1 | 26 = 3·7 + 5 | 3 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
最後の非ゼロの余りは 1 なので、\(\gcd(7, 26) = 1\) であり、逆元は存在します。
3 行目から後退代入を始めます。
$$1 = 5 - 2\cdot 2$$
2 行目より \(2 = 7 - 1\cdot 5\) を代入します。
$$1 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7$$
1 行目より \(5 = 26 - 3\cdot 7\) を代入します。
$$1 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$$
よって \(x = -11\) です。法 26 で整理すると \(-11 + 26 = \)15 となります。
検算:\(7 \cdot 15 = 105 = 4\cdot 26 + 1\) なので、\(105 \bmod 26 = 1\) です。✓
逆数と剰余逆元の比較:例の入力値
逆数 \(1/a\) は、0 でないすべての実数について存在します。一方、剰余逆元は \(a\) と \(m\) が互いに素である場合にのみ存在します。両者は異なる量です。
| a | 法 m | 逆数 1/a | 剰余逆元 | 備考 |
|---|---|---|---|---|
| 3 | 11 | 0.3333 | 4 | 3·4 = 12 ≡ 1 (mod 11) |
| 4 | 8 | 0.25 | なし | gcd(4, 8) = 4(1 ではない) |
| 7 | 26 | 0.142857 | 15 | 7·15 = 105 ≡ 1 (mod 26) |
| −3 | 11 | −0.3333 | 7 | −3 を法 11 で整理すると 8 になり、8·7 = 56 ≡ 1 (mod 11) |
| 0 | 任意の m > 1 | 定義されない | なし | 0·x は常に 0 であり、1 にはならない |
逆数は法を考慮しません。一方、剰余逆元は 0 から \(m-1\) の範囲の整数であり、\(\gcd(a, m) = 1\) の場合にのみ存在します。
よくある質問
なぜ 0 には逆元がないのですか? どんな数に 0 を掛けても結果は 0 になり、決して 1 にはならないためです。
モジュラ逆数が存在しないのはどんなときですか? \(\gcd(a, m) \neq 1\) のときです。たとえば 4 は mod 8 における逆元を持ちません。両者が約数 4 を共有しているからです。
モジュラ逆数に負の数を使えますか? はい。逆元を求める前に、まず 0 から \(m-1\) の範囲に変換してから計算します。