欧拉函数

$$\phi (n)$$

小于 n 的与 n 互素的正整数的个数

---

$$\phi (ab)=\phi (a)\phi (b)$$

根据上面的等式，如果 $m=p_1^{k_1}{p}_2^{k_2}\dots$

则

$$\phi (m)=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots$$ $$\phi (p^i)=p^i-p^{i-1}=p^i\left(1-\frac{1}{p}\right)$$

---

若 $m>2$ ，则结果为偶数

• 对于大于 2 的素数，欧拉函数是偶数
• 对于大于 2 的素数的任意次幂，$p^i-p^{i-1}$ 为偶数

然后分解可以得出

---

$$\sum _{d|n}\phi (d)=n$$