投稿  »  2019-12-26

$\phi$関数と冪乗

概略

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

詳細

$\phi$関数とは

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

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

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

オンライン整数列大辞典

できること

(フェルマーの小定理)

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

そこで,

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