環$R$の要素$a \in R$に対し、$a b = 1$となるような要素$b$を$a$の逆元(inverse)と呼ぶ。 逆元は存在するなら一意である。そこで、逆元の存在する要素に対しては$a^{-1}$として逆元を表すことにする。 逆元が存在する要素を"unit"と呼ぶ。unitのみを集めたものに対して掛け算を演算とするとそれは群になり、これをを$R^*$として表す。

剰余環の場合

剰余環$R = \mathbb{Z}/m\mathbb{Z}$の要素$a \in R$がunitであるのは、$\gcd(a, m) = 1$であることと同値である。 そのような要素に対しては、拡張ユークリッドの互除法を用いて逆元を求めることができる。

${\rm mod}\ p^q$上の場合

ニュートン法(Hansel listing)を用いれば拡張ユークリッドの互除法を使うより高速に逆元を求められる。 特に、${\rm mod}\ 2^k$上の場合は重要である。

多項式の剰余環の場合

多項式の場合でも整数の場合と同じように拡張ユークリッドの互除法で逆元を求められる。

formal power series上の場合

多項式を使うテクニックたち参照。

多数の逆元を一度に求める

長さ$N$の配列$A$に対して、それぞれの要素に対する逆元を全て求めたい。 このとき、1つずつ逆元を求めなくても、逆元を1回だけ計算すれば全ての逆元を求められる。 まず、$p[k] = \displaystyle \prod_{i=0}^{k-1} A[i]$とprefix productを求める。 次に、$p[N]^{-1}$を(普通に)求める。すると、$i < N$に対して$p[i]^{-1} = p[i+1]^{-1} A[i]$として、prefix productの逆元を全て求められる。 最後に、$A[i]^{-1} = p[i+1]^{-1} p[i]$とすれば$A$の全ての逆元を求めることができた。