モジュラ逆数（逆元）計算ツールの使い方
本ツールは、整数 $a$ と法（モジュラス）$m$ を入力するだけで、剰余類環におけるモジュラ逆数（逆元）の計算を自動で行うオンライン計算ツールです。
- 数値の入力: 「整数 $a$」と「法 $m$（$m > 1$）」を入力します。
- 自動リダクション: 入力された $a$ は、まず $a \pmod m$ に変換（余りの計算）されます。
- 最大公約数と存在判定: $a$ と $m$ の最大公約数 $\gcd(a, m)$ を計算し、逆元が存在するかどうかを判定します。
- 結果と計算ステップの表示: $\gcd(a, m) = 1$ の場合、最小の非負整数であるモジュラ逆数 $x$ を出力するとともに、拡張ユークリッドの互除法による途中経過（商と余りの連立方程式、ベズーの等式）をステップ順に表示します。
計算公式と理論 — モジュラ逆数と拡張ユークリッドの互除法
モジュラ逆数（逆元）とは、以下の合同方程式を満たす整数 $x$ のことです。
$$a \times x \equiv 1 \pmod m$$
逆元の存在条件
モジュラ逆数が存在するための必要十分条件は、整数 $a$ と法 $m$ が**互いに素（$\gcd(a, m) = 1$）**であることです。$\gcd(a, m) > 1$ の場合、$a \times x \equiv 1 \pmod m$ を満たす整数 $x$ は存在しません。
拡張ユークリッドの互除法による解法
合同式 $a \times x \equiv 1 \pmod m$ は、ある整数 $y$ を用いて一次不定方程式（ベズーの等式）に書き換えることができます。
$$a \cdot x + m \cdot y = 1$$
この方程式の整数解 $(x, y)$ は、拡張ユークリッドの互除法（Extended Euclidean Algorithm）を用いることで効率的に求めることができます。得られた解 $x$ に対して $x \pmod m$ を計算（負の値の場合は $m$ を加算）することで、範囲 $0 \le x < m$ に含まれるモジュラ逆数が求まります。
また、法 $m$ が素数の場合はフェルマーの小定理（$a^{m-1} \equiv 1 \pmod m$）を利用して $a^{m-2} \pmod m$ を計算することでも逆元を求められますが、拡張ユークリッドの互除法は $m$ が素数でない場合でも $\gcd(a, m) = 1$ であれば適用できる汎用的な手法です。
モジュラ逆数計算機の活用シーン
- 競技プログラミング・アルゴリズム学習: C++ や Python での
modinv関数実装の動作確認や、MOD 演算を伴う組合せ計算（$n\mathrm{C}_r \pmod{10^9+7}$ など）の検証。 - 暗号理論・情報セキュリティ: RSA 暗号や楕円曲線暗号（ECC）における秘密鍵生成や解読アルゴリズムの計算検証。
- 数論・代数学の学習: 大学や高校数学における「合同式」「一次不定方程式」「ユークリッドの互除法」の具体的な計算プロセスの理解。
ブラウザ上で即座に結果と途中式が確認できるため、試験対策やプログラミングのデバッグにぜひご活用ください。