逆数
合同式において逆数を考えることができる。a × b を m で割ると 1 余るとき、b を a の m を法とする逆数と呼ぶ。合同式で表すと以下のようになる。
a × b ≡ 1 ( mod m ) . {\displaystyle a\times b\equiv 1{\pmod {m}}.}
例えば、4 × 2 ≡ 1 (mod 7) となるので、法 7 において 2 は 4 の逆数である。通常の逆数と同様、逆数の逆数は同じ数であり、0 の逆数は存在せず、1 や −1 の逆数はそれ自身である。合同式の性質から、m の倍数の逆数は存在せず、(km ± 1) の逆数はそれ自身になる。
定義上、a は m と互いに素である必要がある。つまり、一般に合同式での逆数は存在するとは限らない。例えば、7 × b ≡ 1 (mod 42) や 12 × b ≡ 1 (mod 4) を満たす b は存在しない。
素数 p を法とする場合、0 以外の全ての元が逆数を持つ。法 17 を例とすると次のようになる。
合同式での逆数はオイラーの定理によって計算できる。a に逆数 b が存在するならば