\phi関数と冪乗

概略

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

詳細

\phi関数とは

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

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

オンライン整数列大辞典

できること

\displaystyle a^{p-1}\equiv 1{\pmod {p}} (フェルマーの小定理)

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

そこで,
\displaystyle a^b \equiv a^{b \mod \phi(n)} \pmod {n}
が成り立つ.これによって大きな数の冪乗が小さいオーダーで可能となる.