日別: 2018年11月11日

個人的メモ

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

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

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

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

具体例

個人的なメモ

• フェルマーの小定理とは次の関係を言う: 素数 p と p とは互いに素な整数 a について a^p-1≡1 (mod p) が成り立つ.
• 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 n と n とは互いに素な整数 a について a^φ(n)≡1 (mod n) が成り立つ.
  • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
  • n=Π_k=1^mp_k^b_k と素因数分解できたならば, φ(n)=nΠ_k=1^m(1-1/p_k)
• カーマイケルの定理とは次の関係を言う: φ(n) は a^m≡1(mod n) を満たす最小の m であるとは限らない.
  最小の m はカーマイケル関数λ(n)で与えられる.
  • カーマイケル関数は次のように再帰的に定義される.
    • λ(2^e)=1 (e=1), 2 (e=2), 2^e-2 (e≧3)
    • 奇素数 p について λ(p^e)=p^e-1(p-1)
    • n=Π_k=1^mp_k^b_k と素因数分解できたならば λ(n)=lcm(λ(p₁^b₁),...,λ(p_m^b_m)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

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

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