浅谈欧拉函数
求法
设一个数x的各质因子为$p_1,p_2,...,p_n$
则$\phi(x)=x-\frac{x}{p_1}-\frac{x}{p_2}-...-\frac{x}{p_n}+\frac{x}{p_1*p_2}+\frac{x}{p_2*p_3}+...=x*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*...*\frac{p_n-1}{p_n}$
性质
性质1
若$n,m$互质，则$\phi(n*m)=\phi(n)*\phi(m)$
证明
若$n$与$m$互质，则$n$与$m$没有相同的质因子设$n$的质因子个数为$cnt_n，m$的质因子个数为$cnt_m$，$p_i$是$n,m$的质因子，则
$\phi(n)*\phi(m)=n*\prod_{i=1}^{cnt_n}(1-p_i)*m*\prod_{i=1}^{cnt_m}(1-p_i)=\phi(n*m)$
性质2
若$p$为质数，则$\phi(p)=p-1$
证明
在$1\sim p-1$中，所有的数与$p$互质，故$\phi(p)=p-1$