合同式に関する諸性質

個人的なメモ

  • フェルマーの小定理とは次の関係を言う: 素数 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 である.

コメントを残す