モジュラ逆数（逆元）計算ツール
整数 a の法 m に関する逆数 x（a かける x が m を法として 1 に合同）を、拡張ユークリッドの互除法で求めます。最大公約数による存在判定と計算過程つき。
入力
整数 a と法 m を入力すると、a の m に関するモジュラ逆数 x（a x が m を法として 1）を拡張ユークリッドの互除法で求めます。
逆数を求めたい整数。負の値も可。
2 以上の整数。
計算結果
3 の 11 を法とする逆数
4
検算: 3 かける 4 を 11 で割った余りは 1
最大公約数 gcd(a, m)
1
逆数の存在
あり
正規化した a
3
拡張ユークリッドの互除法
各段で被除数を除数で割り、商と余りを求めます。余りが 0 になると最大公約数が確定します。
| 被除数 | 除数 | 商 | 余り |
|---|---|---|---|
| 3 | 11 | 0 | 3 |
| 11 | 3 | 3 | 2 |
| 3 | 2 | 1 | 1 |
| 2 | 1 | 2 | 0 |
ベズー係数
3 かける 4 たす 11 かける -1 イコール 1
モジュラ逆数 x は a x が m を法として 1 に合同となる整数で、a と m の最大公約数が 1 のときだけ存在します。係数 s を 0 以上 m 未満に正規化したものが逆数です。
モジュラ逆数は RSA 暗号などで使われ、公開指数の逆数からオイラー関数の値を法として秘密指数を求めます。
計算方法・使い方
- モジュラ逆数 x とは、a かける x を m で割った余りが 1 になる整数のことです。式で書くと a x が m を法として 1 に合同（0 以上 m 未満の x）です。
- 逆数が存在するのは a と m が互いに素、つまり最大公約数 gcd(a, m) が 1 のときに限ります。gcd が 1 でなければ逆数は存在しません。
- 計算には拡張ユークリッドの互除法を使います。これは gcd(a, m) を求めると同時に、a s たす m t イコール gcd を満たす係数 s と t を求める方法です。
- gcd が 1 のとき、係数 s が逆数になります。負になる場合は m を足して 0 以上 m 未満に正規化します。
- 入力の a は m を法として正規化（0 以上 m 未満に還元）してから計算します。負の a も扱えます。
- モジュラ逆数は RSA 暗号の鍵生成などで使われます。公開指数 e の逆数を、オイラー関数の値を法として求めることで秘密指数 d を計算します。
関連する計算ツール
余り計算（剰余・モジュロ）
数学被除数 a を除数 b で割ったときの商と余り（a mod b）を求めます。切り捨て・床・ユークリッド剰余の各定義と、負の数の扱いも表示します。
計算する →最大公約数・最小公倍数 計算（GCD・LCM）
数学複数の整数の最大公約数(GCD)と最小公倍数(LCM)を、ユークリッドの互除法で一発計算。計算過程の表や互いに素かの判定も表示します。
計算する →逆数ガンマ関数 1/Γ(x) 計算ツール
数学実数 x を入力すると、ガンマ関数の逆数 1/Γ(x) を計算します。1/Γ(x) は全実数で定義される整関数で、0 や負の整数ではちょうど 0 になります。Γ(x) の参考値とグラフも表示します。
計算する →ベクトルのノルム計算機
数学n次元ベクトルの成分を入力して、L2（ユークリッド）・L1（マンハッタン）・L∞（最大値）ノルムと単位ベクトルを一括計算します。
計算する →
お客様の声
このツールを使った感想をお聞かせください。
レビューを投稿する
- ホーム
モジュラ逆数（逆元）計算ツール