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

\phi関数と冪乗

概略

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

詳細

\phi関数とは

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

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

オンライン整数列大辞典

できること

a^{p-1}\equiv 1{\pmod {p}}


(フェルマーの小定理)

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

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

そこで,

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


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