乗法逆元(逆数)計算機

乗法逆元(逆数)計算機

成長中 AI Skill PRO

計算を入力してください

通常の逆数 1/a を求めるには 0 のままか空欄にしてください。

公式

数 (a)·a−1≡1(mod法 (m))\text{数 (a)} \cdot a^{-1} \equiv 1 \pmod{\text{法 (m)}}
利用統計

広告

結果

のモジュラ逆元 3 mod 11
4
a · x ≡ 1 (mod m)
入力した数 (a) 3
法 (m) 11
逆数 (1/a) 0.333333

このページの誤りを報告

乗法逆元とは?

ある数の乗法逆元とは、その数に掛け合わせると 1 になる値のことです。普通の実数 \(a\) の場合、逆元は単純にその逆数 \(1/a\) になります。たとえば 4 の逆元は 0.25 です。\(4 \times 0.25 = 1\) となるためです。なお、0 に逆元は存在しません。どんな数を 0 に掛けても 1 にはならないからです。

ある数とその逆数を掛けて1になる様子を示す数直線
逆数 \(1/a\) は、\(a\) に掛けると 1 になる数です。

モジュラ逆数(合同式の逆元)

合同算術(モジュラ計算)における \(a\) の乗法逆元(mod \(m\))とは、$$\text{Number (a)} \cdot a^{-1} \equiv 1 \pmod{\text{Modulus (m)}}$$ を満たす 0 から \(m-1\) の範囲の整数 \(x\) のことです。これは整数論や暗号理論(RSA、ハッシュ、誤り訂正符号など)で頻繁に登場します。モジュラ逆数が存在するのは、\(a\) と \(m\) が互いに素なとき、つまり \(\gcd(a, m) = 1\) のときに限られます。この計算機は拡張ユークリッドの互除法を用いて逆元を求めます。

広告
ある数とその逆数の積が一周して1になる様子を示す合同算術の時計の文字盤
モジュラ逆数 \(x\) は \(a \cdot x \equiv 1 \pmod{m}\) を満たし、\(m\) 個の位置をもつ時計を一周する様子で示されます。

この計算機の使い方

まず数 \(a\) を入力します。法(modulus)を 0 のまま(または空欄)にすると、通常の逆数 \(1/a\) が求められます。モジュラ逆数を計算したい場合は、1 より大きい法 \(m\) を入力してください。計算機は \(a\) を \(m\) で割った余りに変換したうえで逆元を返します。\(a\) と \(m\) に共通の約数がある場合は、逆元が存在しないことを表示します。

計算例

3 の mod 11 における逆元を求めてみましょう。\(3x \equiv 1 \pmod{11}\) を満たす \(x\) が必要です。\(x = 4\) を試すと $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}$$ となります。したがってモジュラ逆数は 4 です。一方、逆数としての 3 の逆元は \(1/3 \approx 0.333333\) になります。

拡張ユークリッドの互除法で手計算する剰余逆元

法 \(m\) における \(a\) の剰余逆元とは、\(a \cdot x \equiv 1 \pmod{m}\) を満たす数 \(x\) のことです。これは \(\gcd(a, m) = 1\) のときに限って存在します。拡張ユークリッドの互除法を使えば、この \(x\) を求めることができます。

  1. ユークリッドの互除法を実行する。\((m, a)\) の組に対して繰り返し割り算を行い、組 \((m, a)\) を \((a, r)\) に置き換えます。ここで \(r\) は余りです。余りが 0 になるまで続けます。
  2. 最大公約数を確認する。最後の非ゼロの余りが \(\gcd(a, m)\) です。これが 1 でなければ逆元は存在しないので、ここで終了します。
  3. 割り算の各行を逆にたどって代入する(後退代入)。\(1 = a \cdot x + m \cdot y\) の形に書き直します。
  4. \(x\) を法 \(m\) で 0 から \(m-1\) の範囲に収める。\(x\) が負の場合は \(m\) を加えます。
  5. 検算する。\(a \cdot x \bmod m = 1\) となることを確かめます。

例:法 26 における 7 の剰余逆元。

行 割り算 商 余り
1 26 = 3·7 + 5 3 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

最後の非ゼロの余りは 1 なので、\(\gcd(7, 26) = 1\) であり、逆元は存在します。

3 行目から後退代入を始めます。

$$1 = 5 - 2\cdot 2$$

2 行目より \(2 = 7 - 1\cdot 5\) を代入します。

$$1 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7$$

1 行目より \(5 = 26 - 3\cdot 7\) を代入します。

$$1 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$$

よって \(x = -11\) です。法 26 で整理すると \(-11 + 26 = \)15 となります。

検算:\(7 \cdot 15 = 105 = 4\cdot 26 + 1\) なので、\(105 \bmod 26 = 1\) です。✓

広告

逆数と剰余逆元の比較:例の入力値

逆数 \(1/a\) は、0 でないすべての実数について存在します。一方、剰余逆元は \(a\) と \(m\) が互いに素である場合にのみ存在します。両者は異なる量です。

a 法 m 逆数 1/a 剰余逆元 備考
3 11 0.3333 4 3·4 = 12 ≡ 1 (mod 11)
4 8 0.25 なし gcd(4, 8) = 4(1 ではない)
7 26 0.142857 15 7·15 = 105 ≡ 1 (mod 26)
−3 11 −0.3333 7 −3 を法 11 で整理すると 8 になり、8·7 = 56 ≡ 1 (mod 11)
0 任意の m > 1 定義されない なし 0·x は常に 0 であり、1 にはならない

逆数は法を考慮しません。一方、剰余逆元は 0 から \(m-1\) の範囲の整数であり、\(\gcd(a, m) = 1\) の場合にのみ存在します。

よくある質問

なぜ 0 には逆元がないのですか? どんな数に 0 を掛けても結果は 0 になり、決して 1 にはならないためです。

モジュラ逆数が存在しないのはどんなときですか? \(\gcd(a, m) \neq 1\) のときです。たとえば 4 は mod 8 における逆元を持ちません。両者が約数 4 を共有しているからです。

モジュラ逆数に負の数を使えますか? はい。逆元を求める前に、まず 0 から \(m-1\) の範囲に変換してから計算します。

最終更新:

数学と統計で人気の電卓

数学と統計の電卓をすべて見る