欧拉函数

令 (N=p_1^{c_1}p_2^{c_2}...p_m^{c_m})

则(varphi(n)=N imes prod_{prime_p|N}(1-frac{1}{p}))

关于欧拉函数：

①(forall n>1 ,sumlimits_{i=1,gcd(i,n)=1}^ni=frac{n}{2} imes varphi(n))

②(gcd(a,b)=1,varphi(ab)=varphi(a)varphi(b))

③若(f(ab)=f(a) imes f(b)),当(n=prod_{i=1}^mp_i^{c_i}),则(f(n)=prod_{i=1}^mf(p_i^{c_i}))

④当(p)为质数时，且(p|n,p^2|n),则(varphi(n)=varphi(frac{n}{p}) imes p)

⑤当(p)为质数时，且(p|n,p^2!|n),则(varphi(n)=varphi(frac{n}{p}) imes (p-1))

⑥(sum_{d|n}varphi(d)=n)