モジュラ逆数
整数 3 の法 11 に関するモジュラ逆数 x を求める。これは
3 − 1 ≡ x ( mod 11 ) {\displaystyle 3^{-1}\equiv x{\pmod {11}}}
を満たすものを計算するということだが、その意味は
3 x ≡ 1 ( mod 11 ) {\displaystyle 3x\equiv 1{\pmod {11}}}
なる x を求めることに他ならない。 Z / 11 Z {\displaystyle \mathbb {Z} /11\mathbb {Z} } においてこの合同式の解 x が 4 mod 11 であることは
3 × 4 = 12 ≡ 1 ( mod 11 ) {\displaystyle 3\times 4=12\equiv 1{\pmod {11}}}
から明らかであり、従って 11 を法として 3 の逆数は 4 である。こうして Z / 11 Z {\displaystyle \mathbb {Z} /11\mathbb {Z} } において逆数が求まったが、上記の合同式を満たす x は 4 のみではない。残りの解は、得られた 4 に m=11 の倍数を加えたものとして得られる。一般にこの例において x となり得る整数は
4 + 11 z , z ∈ Z {\displaystyle 4+11z,z\in \mathbb {Z} }
の形をしており、これは {..., -18, -7, 4, 15, 26, ...} という集合を成す。
リストの各要素に k − 1 {\displaystyle k^{-1}} を掛け、下位 w bit に相当する部分を取り出す(つまり 2 w {\displaystyle 2^{w}} で割った余りをとる)。
除算をハードウェアで実装していない処理系にとって、除算は掛け算に比べて遅く、この方法によって格段に処理速度を速めることができる。手順1.には時間はかかるが1回で済むため、扱うリストのサイズが大きければそれだけ効率的である。
このほかモジュラ逆数を用いて、中国の剰余定理によって存在が保証されている合同方程式の解を求めることができる。
例えば、合同方程式
X ≡ 4 ( mod 5 ) {\displaystyle X\equiv 4{\pmod {5}}}
X ≡ 4 ( mod 7 ) {\displaystyle X\equiv 4{\pmod {7}}}
X ≡ 6 ( mod 11 ) {\displaystyle X\equiv 6{\pmod {11}}}
は 5, 7, 11 が互いに素であり解をもつ。解は