ふわわあのへや競プロとか、好きなこと、いろいろ。

φ関数と冪乗

概略

  1. 冪乗のmodをとりたい!
  2. 指数部分は普通にmod取っちゃだめだよ!
  3. ϕ\phi関数を通そうね

詳細

ϕ\phi関数とは

オイラーのトーシェント関数という名前.(Euler's totient function)
オイラーさんの研究の成果らしい.
ϕ(n)\phi(n)をn未満の正の整数のうちnと互いに素であるものの個数と定義する.

このとき,次の性質が成り立つ

  • gcd(n,m)=1ϕ(nm)=ϕ(n)ϕ(m)\gcd(n,m)=1 \Rightarrow \phi(nm)=\phi(n)\phi(m)
  • ppが素数ならばϕ(p)=p1\phi(p)=p-1

オンライン整数列大辞典

できること

ap11(modp)a^{p-1}\equiv 1{\pmod {p}}

(フェルマーの小定理)

後にオイラーはこの定理を拡張した.
a を n と互いに素な整数のときこれが成り立つ.
(nは素数でなくても良い.)

aφ(n)1(modn)a^{\varphi (n)}\equiv 1{\pmod {n}}

そこで,

ababmodϕ(n)(modn)a^b \equiv a^{b \mod \phi(n)} \pmod {n}

が成り立つ.これによって大きな数の冪乗が小さいオーダーで可能となる.