モジュラ逆数とは?
整数 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を法とする逆元とは、\(a \cdot x \equiv 1 \pmod{m}\) を満たす数xのことです。これは \(\gcd(a, m) = 1\) のときにのみ存在します。拡張ユークリッドの互除法では、次の3つの手順でこれを求めます。
- 繰り返し割り算。 mをaで割り、次に前の除数を余りで割る、というように余りが0になるまで続けます。最後の0でない余りがgcdです。これが1でなければ、逆元は存在しません。
- 1を組み合わせで表す。 後退代入(back-substitution)を行うか、計算の途中で係数を追跡して、\(1 = a \cdot x + m \cdot y\) の形に書き表します。これがベズーの等式です。
- xを簡約する。 \(x \bmod m\) を求めます。xが負の場合は、mを加えて(必要なら繰り返して)0からm − 1の範囲に収めます。
計算例:a = 7, m = 40。
| 手順 | 割り算 | 商 q | 余り |
|---|---|---|---|
| 1 | 40 = 5·7 + 5 | 5 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
最後の0でない余りは1なので、\(\gcd(7, 40) = 1\) となり、逆元は存在します。
後退代入:
$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$
したがって \(7 \cdot (-17) + 40 \cdot 3 = 1\) となり、\(x = -17\) が得られます。
反復による検算(aの係数t): \(t_0 = 0\)(m = 40の場合)、\(t_1 = 1\)(a = 7の場合)から始め、\(t_{k+1} = t_{k-1} - q_k \, t_k\) を使います。
| 余り | 使用した q | t |
|---|---|---|
| 40 | – | 0 |
| 7 | – | 1 |
| 5 | 5 | 0 − 5·1 = −5 |
| 2 | 1 | 1 − 1·(−5) = 6 |
| 1 | 2 | −5 − 2·6 = −17 |
余りが1になった行では \(t = -17\) となります。これを簡約すると:\(-17 + 40 = \)23。
検証: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\) なので、\(161 \bmod 40 = 1\)。✓
同じ方法は、より大きな数にも使えます。a = 17, m = 3120 の場合、x = 2753 が得られます。なぜなら \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\) だからです。この組み合わせは、RSAの教科書的な古典例として知られています。
入力例とその逆元
以下の各逆元は \((a \cdot x) \bmod m = 1\) を満たします。\(\gcd(a, m) > 1\) の場合、逆元は存在しません。
| a | m | gcd(a, m) | 逆元 x | 検算 |
|---|---|---|---|---|
| 3 | 11 | 1 | 4 | 3·4 = 12 = 1·11 + 1 |
| 7 | 26 | 1 | 15 | 7·15 = 105 = 4·26 + 1 |
| 5 | 12 | 1 | 5 | 5·5 = 25 = 2·12 + 1 |
| 10 | 17 | 1 | 12 | 10·12 = 120 = 7·17 + 1 |
| 17 | 3120 | 1 | 2753 | 17·2753 = 46801 = 15·3120 + 1 |
| 4 | 6 | 2 | なし | 4x mod 6 は常に偶数であり、1にはならない |
| 6 | 9 | 3 | なし | 6x mod 9 は常に3の倍数であり、1にはならない |
5は12を法として自分自身が逆元であることに注目してください。一般に、\(x^2 \equiv 1 \pmod{m}\) は1以外の解を持つことがあるため、自分自身が逆元となる数も存在します。
重要用語:互いに素、GCD、合同式と剰余類
- 法(モジュラス、m): 時計の文字盤のように、値が一周して戻る基準となる正の整数です。
- 合同(≡): \(a \equiv b \pmod{m}\) は、mが \(a - b\) を割り切ることを意味し、aとbをmで割ったときの余りが等しいことを表します。
- GCD(最大公約数): 両方の数を割り切る最大の整数です。
- 互いに素(coprime、relatively prime): gcdが1である2つの整数です。これは剰余逆元が存在するための条件そのものです。
- ベズーの等式: 整数aとmに対して、\(a \cdot x + m \cdot y = \gcd(a, m)\) を満たす整数xとyが存在します。gcdが1のとき、この式をmを法として考えると \(a \cdot x \equiv 1\) が得られるので、xが逆元になります。
- 剰余類: mを法として同じ余りを持つ整数全体の集合です。逆元は剰余類として一意に定まり、計算機は0からm − 1までの代表値を返します。
- 乗法的逆元(剰余): \(a \cdot x \equiv 1 \pmod{m}\) を満たす剰余 \(x = a^{-1} \bmod m\) です。
オイラーの定理: \(\gcd(a, m) = 1\) のとき、\(a^{\varphi(m)} \equiv 1 \pmod{m}\) が成り立ちます。ここで \(\varphi\) はオイラーのトーシェント関数です。したがって、逆元は \(a^{\varphi(m)-1} \bmod m\) としても計算できます。
フェルマーの小定理: m = p が素数のとき、\(\varphi(p) = p - 1\) なので、pで割り切れない任意のaについて \(a^{-1} \equiv a^{p-2} \pmod{p}\) が成り立ちます。例:\(3^{9} = 19683 = 1789 \cdot 11 + 4\) なので、\(3^{-1} \equiv 4 \pmod{11}\) となり、上の表と一致します。べき乗の公式では(\(\varphi\) を求めるために)mの素因数分解が必要ですが、拡張ユークリッドの互除法では不要です。そのため、一般の法に対しては通常こちらの方が高速な方法です。
よくある質問
逆元が存在しないのはどんなとき? a と m が 1 より大きい公約数を持つときです。たとえば 6 を法とする 4(\(\gcd = 2\))には逆元がありません。
m は素数でなければなりませんか? いいえ。m は 2 以上の任意の整数で構いません。重要なのは a と m が互いに素であることだけです。
答えはどの範囲で得られますか? 逆元は最小の非負の剰余として、\(0\) から \(m - 1\) の範囲で与えられます。