モジュラ逆数

合同算術におけるモジュラ逆数（モジュラぎゃくすう、）は、与えられた整数 と法 に関して
という関係にある整数 の属する合同類（あるいはその標準的な代表元）をいう。即ち、整数の法 に関する合同類環 formula_2 における乗法逆元である。この式は
と書いても同じである。ある種の応用においては、モジュラ逆数 が formula_2 に属さないような場合を考えることもある。
 の を法とする逆数が存在するための必要十分条件は と とが互いに素（即ち、最大公約数 が ）となることである。法 に関する のモジュラ逆数が存在するならば、 を法とした による除法（「余り付き除法」ではない）を、モジュラ逆数を掛けることとして定義することができる。
例.
整数 の法 に関するモジュラ逆数 を求める。これは
を満たすものを計算するということだが、その意味は
なる "x" を求めることに他ならない。formula_7 においてこの合同式の解 が であることは
から明らかであり、従って を法として の逆数は である。こうして formula_7 において逆数が求まったが、上記の合同式を満たす は のみではない。残りの解は、得られた に の倍数を加えたものとして得られる。一般にこの例において となり得る整数は
の形をしており、これは という集合を成す。
逆数計算.
拡張ユークリッド互除法.
法 に関する のモジュラ逆数は、拡張ユークリッド互除法を用いて計算することができる。互除法のアルゴリズムはベズーの等式
の解を求めるものである。ただし、 が既知で、整数 および がこのアルゴリズムから求まる。
さて、モジュラ逆数は合同式
の解であったから、合同式の定義により （ は の約数）、即ち適当な整数 を用いて
となる。これを整理した
は、 と が既知で、逆数となる と捨てられる は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば が「求まる」のではなくて「所与」であること程度で、それゆえ が と互いに素でなければならず、さもなくば逆元 は存在しない。
このアルゴリズムの計算量は と仮定すると で、一般に冪乗の計算よりも効率的である。
オイラーの定理の利用.
拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる。
オイラーの定理によれば、 が と互いに素ならば、オイラー函数 に対して
が成り立つ。これは が法 に関する既約合同類群 formula_16 に入るための必要十分条件が が と互いに素であることから従う。従って、モジュラ逆数が直接的に
と求まる。これから、 が素数である特別の場合には、 ゆえ
となる。この方法は一般には拡張ユークリッド互除法よりも遅いが、冪剰余の実装が使える場合には利用されることがある。この方法が不利な点としては、
応用.
モジュラ逆数を見つけるという操作は、モジュラ計算を使ったアルゴリズムに多く応用されている。例えば、暗号技術ではモジュラ演算を用いることで、演算をより早く、より少ない記憶容量で行う部分と、演算がより困難な部分がある。これら二つの性質は共に利点として利用できる。特にRSA暗号では、暗号化・復号には適切に選ばれたモジュラ逆数となる2つの数が使われる。2つのうち1つは公開し、暗号化するために使用される。もう1つは安全に保管しておき、復号に使用する。ここまでの処理は高速だが、1つ目の公開鍵から2つ目の秘密鍵を作るには非現実的な計算コストは避けられないと考えられており、このことがRSA暗号の仕組みを支えている。
ほかの変わった例を一つ挙げる。ワードのサイズの、kの倍数で奇数である整数を要素に持つ（長い）リストがあったとする。ここで、これらの数をすべてkで割りたい。実装の一つとして次のようなものがある。
除算をハードウェアで実装していない処理系にとって、除算は掛け算に比べて遅く、この方法によって格段に処理速度を速めることができる。手順1.には時間はかかるが1回で済むため、扱うリストのサイズが大きければそれだけ効率的である。
このほかモジュラ逆数を用いて、中国の剰余定理によって存在が保証されている合同方程式の解を求めることができる。
例えば、合同方程式 
は 5, 7, 11 が互いに素であり解をもつ。解は
であり
である。上記の合同方程式を満たしていることは容易にわかる。よって
385 は 5, 7, 11 の最小公倍数である。
また、モジュラ逆数はの定義で重要な位置を占めている。