モジュラ逆数について

個人的メモ

m における整数 a のモジュラ逆数 a-1 (mod m) とは, aa-1≡1 (mod m) を満たす a-1x (mod m) なる整数 x の合同類である.

m における整数 a のモジュラ逆数が存在するための必要十分条件は gcd(m, a)=1 である.

a-1 (mod m) を求める最も汎用的な方法は拡張されたユークリッドの互除法を用いることである. つまり, a, m が所与であるもとでの ax-qm=gcd(a,m)=1 を満たす xa-1 (mod m) である.

他にも, オイラーのトーシェント関数を用いて a-1aφ(m)-1 (mod m) としたり, カーマイケル関数を用いて a-1aλ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a-1ap-2 (mod p) とすることができる.

具体例

合同式に関する諸性質

個人的なメモ

  • フェルマーの小定理とは次の関係を言う: 素数 pp とは互いに素な整数 a について ap-1≡1 (mod p) が成り立つ.
  • 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 nn とは互いに素な整数 a について aφ(n)≡1 (mod n) が成り立つ.
    • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
    • nk=1mpkbk と素因数分解できたならば, φ(n)=nΠk=1m(1-1/pk)
  • カーマイケルの定理とは次の関係を言う: φ(n) は am≡1(mod n) を満たす最小の m であるとは限らない.
    最小の m はカーマイケル関数λ(n)で与えられる.

    • カーマイケル関数は次のように再帰的に定義される.
      • λ(2e)=1 (e=1), 2 (e=2), 2e-2 (e≧3)
      • 奇素数 p について λ(pe)=pe-1(p-1)
      • nk=1mpkbk と素因数分解できたならば λ(n)=lcm(λ(p1b1),...,λ(pmbm)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

    n≡1 (mod λ(n)) を満たすような n をカーマイケル数という.

以上によれば, 2n≡1 (mod 15) を満たす n は, フェルマーの小定理では導出できない (n=3×5)が,
オイラーの定理によれば n=8 のときに成立することが分かり, カーマイケルの定理によれば, 最小の整数 n は 4 である.