モジュラ逆数（逆元）計算ツール ─ mod m での a の逆元

結果

Modular inverse a^-1 (mod m)

the integer x with a·x ≡ 1 (mod m)

gcd(a, m)	1
剰余の範囲	0 ≤ x < m

モジュラ逆数計算ツールとは？

このツールは、整数 a の m を法としたモジュラ逆数（モジュラ逆元）を求めます。すなわち、$a \cdot x \equiv 1 \pmod{m}$ を満たし、$0 \le x < m$ の範囲にある唯一の整数 x です。計算には拡張ユークリッド互除法を用いており、同時に最大公約数 $\gcd(a, m)$ も得られます。これは純粋な整数論に基づく計算なので、国や地域を問わず結果は同じです。暗号理論（RSA の鍵生成）やハッシュ、一次合同式の求解などで広く活用されています。

使い方

整数 a と、正の法 m を入力します（一意な逆元を得るには $m \ge 2$ を指定してください）。ツールはまず a を m で剰余をとり、拡張ユークリッド互除法を実行して、逆元と $\gcd(a, m)$ を出力します。a と m が互いに素でない場合（$\gcd \ne 1$）は逆元が存在しないため、その旨が表示されます。

計算式の解説

逆元が存在するのは、$\gcd(a, m) = 1$ のとき、かつそのときに限ります。拡張ユークリッド互除法は、$a \cdot s + m \cdot t = \gcd(a, m)$ を満たす整数 s, t を求めます。gcd が 1 のときは $a \cdot s \equiv 1 \pmod{m}$ となるため、逆元は $$x = ((s \bmod m) + m) \bmod m$$ として、最小の非負剰余に正規化して得られます。

a×x が一周して 1 にたどり着く円形のモジュラー環 — 逆数 x は、a*x が法を一周して 1 になる値です。

具体例

$a = 7$、$m = 4$ の場合を考えます。$7 \equiv 3 \pmod{4}$ なので、$3x \equiv 1 \pmod{4}$ を解きます。$(7, 4)$ に拡張ユークリッド互除法を適用すると $\gcd = 1$、ベズー係数 $s = -1$ が得られ、 $$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$ となります。検算すると $7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}$ で確かに成立します。答えは 3 です。