欧拉函数

定义

记欧拉函数 \(\varphi(n)\) 表示 \(1\sim n\) 与 \(n\) 互质的整数的个数。

性质

1. 若 \(p\) 为质数，则 \(\varphi(p^k)=(p-1)\cdot\varphi(p^{k-1})\)。
2. \(\varphi\) 是积性函数。（积性函数 \(f\)：若 \(a,b\) 互质，则满足 \(f(ab)=f(a)\cdot f(b)\)）
3. 若 \(n=\prod_{i=1}^mp_i^{\alpha_i}\)，则 \(\displaystyle \varphi(n)=n\times\prod_{i=1}^m\frac{p_i-1}{p_i}\)。