オイラー関数
1から自然数
$ n
との間で互いに素である自然数の個数を求める関数
素数
$ p
において
$ \phi(p)=p-1
1から
$ p
全部
$ n
と互いに素だから
$ \phi(p^2)=p^2-p
$ p^2
の約数は
$ p
の倍数
つまり
$ 1p
~
$ pp
の
$ p
個
冪乗に一般化すると...
$ \phi(p^k)=p^k-p^{k-1}
二つの素数
$ p
と
$ q
において
$ \phi(p\cdot q)=(p-1)\cdot (q-1)