合同式に関する諸性質

個人的なメモ

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