欧拉函数

定义：

• $\varphi\left(n\right)$，表示小于等于$n$的和$n$互质的数的个数

性质：

1. 积性函数

   对任意满足$\operatorname{\mathrm{gcd}}\left(a,b\right)=1$的整数$a,b$，有$\varphi\left(a,b\right)=\varphi\left(a\right)\cdot\varphi\left(b\right)$

   特别的，当$n$是奇数时$\varphi\left(2n\right)=\varphi\left(n\right)$

2. $n=\sum_{\frac{d}{n}}^{\placeholder{}}\varphi\left(d\right)$ **，****$n$**的所有正约数的欧拉函数之和等于n本身

   如$n=6$，$d=1,2,3,6$

   $ \varphi(1) = 1 $，$ \varphi(2) = 1 $，$ \varphi(3) = 2 $ ，$ \varphi(6) = 2 $ 和为 $6$

3. $n$为质数，欧拉函数值为$n-1$

4. 若$n=p^{k}$，且$p$为质数，那么$\varphi\left(n\right)=p^{k}-p^{k-1}$

   推论：$\varphi\left(p^{k}\right)=p^{k}-p^{k-1}=p\cdot\left(p^{k-1}-p^{k-2}\right)=p\cdot \varphi\left(p^{k-1}\right)$

5. 唯一分解定理：

   设$n=\prod_{i=1}^{s}p_{i}^{k_{i}}$，其中$p_{i}$是质数，有$\varphi\left(n\right)=n\cdot\prod_{i=1}^{s}\frac{p_{i}-1}{p_{i}}$

6. 对于任意不全为0的整数$n,m$，$\varphi\left(nm\right)\cdot\varphi\left(\operatorname{\mathrm{gcd}}\left(n,m\right )\right)=\varphi\left(n\right)\cdot\varphi\left(m\right)\operatorname{\cdot\mathrm{gcd}} \left(n,m\right)$