モジュラ逆数とは？
整数 a の m を法とするモジュラ乗法逆元とは、\((a \cdot x) \bmod m = 1\) を満たす整数 x のことです。これはモジュラ演算における「割り算」に相当し、整数論や RSA 暗号、さらには符号理論の多くのアルゴリズムで中心的な役割を果たします。本計算機は拡張ユークリッドの互除法を用いて x を求めます。
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
この計算機の使い方
数 a と法 m（\(m \ge 2\)）を入力してください。ツールは \(0 \le x < m\) の範囲で最小の非負の逆元 x を返し、逆元が存在するかどうかを判定し、\(\gcd(a, m)\) も表示します。\(\gcd(a, m) \ne 1\) の場合は逆元が存在せず、結果は「なし」と表示されます。
計算式の解説
逆元が存在するのは \(\gcd(a, m) = 1\) のとき、すなわち a と m が互いに素であるときに限られます。拡張ユークリッドの互除法は、\(a \cdot x + m \cdot y = \gcd(a, m)\) を満たす整数 x と y を求めます。gcd が 1 のとき、x を m で割った余りが逆元になります。結果が負の場合は m を加えて正の値に正規化します。
具体例で確認
11 を法とする 3 の逆元を求めてみましょう。\(3x \equiv 1 \pmod{11}\) を満たす x が必要です。試しに計算すると、\(3 \times 4 = 12 = 11 + 1\) なので、\(12 \bmod 11 = 1\) となります。したがって x = 4 です。拡張ユークリッドの互除法でも同じ値が得られ、\(\gcd(3, 11) = 1\) であることから逆元が存在することが確認できます。
よくある質問
逆元が存在しないのはどんなとき？ a と m が 1 より大きい公約数を持つときです。たとえば 6 を法とする 4（\(\gcd = 2\)）には逆元がありません。
m は素数でなければなりませんか？ いいえ。m は 2 以上の任意の整数で構いません。重要なのは a と m が互いに素であることだけです。
答えはどの範囲で得られますか？ 逆元は最小の非負の剰余として、\(0\) から \(m - 1\) の範囲で与えられます。
