モジュラ逆数
X = t 1 ( 7 × 11 ) × 4 + t 2 ( 5 × 11 ) × 4 + t 3 ( 5 × 7 ) × 6 {\displaystyle X=t_{1}(7\times 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6}
であり
t 1 = ( 7 × 11 ) − 1 ( mod 5 ) = 3 {\displaystyle t_{1}=(7\times 11)^{-1}{\pmod {5}}=3}
t 2 = ( 5 × 11 ) − 1 ( mod 7 ) = 6 {\displaystyle t_{2}=(5\times 11)^{-1}{\pmod {7}}=6}
t 3 = ( 5 × 7 ) − 1 ( mod 11 ) = 6 {\displaystyle t_{3}=(5\times 7)^{-1}{\pmod {11}}=6}
である。上記の合同方程式を満たしていることは容易にわかる。よって
X ≡ 3504 ≡ 39 ( mod 385 ) {\displaystyle X\equiv 3504\equiv 39{\pmod {385}}}
385 は 5, 7, 11 の最小公倍数である。
また、モジュラ逆数はKloosterman和(英語版)の定義で重要な位置を占めている。
合同算術において、法 m > 1 に関する整数 a のモジュラ逆数(モジュラぎゃくすう、英: modular multiplicative inverse)とは,
a x ≡ x a ≡ 1 ( mod m ) {\displaystyle ax\equiv xa\equiv 1{\pmod {m}}}
という関係にある整数 x の属する合同類(あるいはその標準的な代表元)のことで、これを a で表す。これは、整数の法 m に関する合同類環 Z / m Z {\displaystyle \mathbb {Z} /m\mathbb {Z} } における乗法逆元である。ある種の応用においては、モジュラ逆数 a が Z / m Z {\displaystyle \mathbb {Z} /m\mathbb {Z} } に属さないような場合を考えることもある。
a の m を法とする逆数が存在するための必要十分条件は a と m とが互いに素(即ち、最大公約数 gcd(a, m) が 1)となることである。法 m に関する a のモジュラ逆数が存在するならば、m を法とした a による除法(「余り付き除法」ではない)を、モジュラ逆数を掛けることとして定義することができる。
法 m に関する a のモジュラ逆数は、拡張ユークリッド互除法を用いて計算することができる。互除法のアルゴリズムはベズーの等式
a x + b y = gcd ( a , b ) {\displaystyle ax+by=\gcd(a,b)}
の解を求めるものである。ただし、a, b が既知で、整数 x, y および gcd(a, b) がこのアルゴリズムから求まる。
さて、モジュラ逆数は合同式
a x ≡ 1 ( mod m ) {\displaystyle ax\equiv 1{\pmod {m}}}
の解であったから、合同式の定義により m | ax − 1(m は ax − 1 の約数)、即ち適当な整数 q を用いて
a x − 1 = q m {\displaystyle ax-1=qm}
となる。これを整理した
a x − q m = 1 {\displaystyle ax-qm=1}
は、a と m が既知で、逆数となる x と捨てられる q は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば gcd(a, m) = 1 が「求まる」のではなくて「所与」であること程度で、それゆえ a が m と互いに素でなければならず、さもなくば逆元 x は存在しない。
このアルゴリズムの計算量は |a| < m と仮定すると O((log m)) で、一般に冪乗の計算よりも効率的である。