モジュラー逆数（乗法逆元）計算ツール

計算を入力してください

整数 a

法 m

結果

乗法逆元

4

a^-1 mod m

gcd(a, m)	1
逆元の有無	あり

モジュラー逆数（mod m の乗法逆元）とは？

整数 a の法 m における乗法逆元とは、\((a \cdot x) \bmod m = 1\) を満たす 1 以上 m−1 以下の整数 x のことです。つまり、a と x を掛けて m で割ったときに、余りがちょうど 1 になる数を指します。これはモジュラー演算における「a で割ること」に相当し、整数論や暗号理論（RSA の鍵生成、ハッシュ、中国剰余定理など）の土台となる重要な概念です。

Modular arithmetic wraps the number line into a circle of m positions.

この計算ツールの使い方

整数 a と法 m（m は 2 以上）を入力してください。本ツールは a を m で約してから拡張ユークリッドの互除法を実行し、逆元が存在すればその値を返します。a が負の数の場合も、0 から m−1 の範囲に自動的に変換して処理します。

計算式の仕組み

逆元が存在するのは、gcd(a, m) = 1 のとき、かつそのときに限ります。これは a と m が 1 以外に共通の約数を持たない（互いに素である）ことを意味します。$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$拡張ユークリッドの互除法は、\(a \cdot s + m \cdot t = \gcd(a, m)\) を満たす整数 s と t を求めます。gcd が 1 のとき、係数 s を m で約した値が逆元になります。gcd(a, m) ≠ 1 の場合は、逆元は存在しません。

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

計算例

3 の法 11 における逆元を求めてみましょう。\((3 \cdot x) \bmod 11 = 1\) を満たす x が必要です。試してみると、$$3 \cdot 4 = 12, \quad 12 \bmod 11 = 1$$となります。したがって逆元は 4 です。\(\gcd(3, 11) = 1\) なので、拡張ユークリッドの互除法でも同じ結果が瞬時に得られます。

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

よくある質問

逆元が存在しないのはどんなとき？ a と m が互いに素でないときです。例えば 4 は法 8 における逆元を持ちません。\(\gcd(4, 8) = 4 \ne 1\) だからです。

法は素数でなければいけませんか？ いいえ。a がその法と互いに素でありさえすれば、どんな法でも構いません。m が素数の場合は、1 から m−1 までのすべての非ゼロの a が逆元を持ちます。

結果が常に 1 から m−1 の間になるのはなぜ？ 逆元を m で約して、最小の正の代表値（標準的な形）に揃えているためです。