合同式での逆数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:38 UTC 版)
詳細は「モジュラ逆数」を参照 合同式において逆数を考えることができる。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 を例とすると次のようになる。 元0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 逆数なし 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16 合同式での逆数はオイラーの定理によって計算できる。a に逆数 b が存在するならば a × b ≡ 1 ≡ a φ ( m ) = a × a φ ( m ) − 1 ( mod m ) {\displaystyle a\times b\equiv 1\equiv a^{\varphi (m)}=a\times a^{\varphi (m)-1}{\pmod {m}}} なので、 b ≡ a φ ( m ) − 1 ( mod m ) {\displaystyle b\equiv a^{\varphi (m)-1}{\pmod {m}}} （ここで φ はオイラーのφ関数）であり、逆に a と m が互いに素であれば、この式によって逆数が与えられる。特に、m が素数の場合以下のようになる（フェルマーの小定理から直接導かれる）。 b ≡ a m − 2 ( mod m ) . {\displaystyle b\equiv a^{m-2}{\pmod {m}}.} また、ユークリッドの互除法によっても効率的に求めることができる。定義式は、以下のベズーの等式（ディオファントス方程式の一種）が b と n について整数解を持つことと同値である。 a × b + m × n = 1. {\displaystyle a\times b+m\times n=1.} この式の解は、a と m が互いに素である場合、かつその場合に限り存在する。
※この「合同式での逆数」の解説は、「逆数」の解説の一部です。
「合同式での逆数」を含む「逆数」の記事については、「逆数」の概要を参照ください。
- 合同式での逆数のページへのリンク
