乗法逆元とは？
ある数の乗法逆元とは、その数に掛け合わせると 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\) になります。
よくある質問
なぜ 0 には逆元がないのですか？ どんな数に 0 を掛けても結果は 0 になり、決して 1 にはならないためです。
モジュラ逆数が存在しないのはどんなときですか？ \(\gcd(a, m) \neq 1\) のときです。たとえば 4 は mod 8 における逆元を持ちません。両者が約数 4 を共有しているからです。
モジュラ逆数に負の数を使えますか？ はい。逆元を求める前に、まず 0 から \(m-1\) の範囲に変換してから計算します。
