问题及解答

Euler's totient function $\phi(m)$ 定义为 $\{1,2,3,\ldots,m-1\}$ 中与 $m$ 互素的元素个数.

显然对于素数 $p$, 有 $\phi(p)=p-1$.

证明: $\phi(2p)=p-1$.

问 $\phi(p^2)$ 等于多少?

事实上, Euler phi function 具有乘积性, 如果 $(m,n)=1$, 则

\[
\phi(mn)=\phi(m)\phi(n).
\]

Euler 证明

\[
\frac{\phi(n)}{n}=\prod_{p|n}(1-\frac{1}{p}),
\]

这里 $p$ 取遍 $n$ 的所有素因子.

有了这个公式, 就很容易计算一个正整数在欧拉函数下的值.

Reference:

https://en.wikipedia.org/wiki/Euler's_totient_function