一、定义
欧拉函数 \(\varphi(n)\)表示1~n中与n互质的个数
二、性质
以下涉及的数均为数论数.
1.设p为素数,则\(\varphi(p)=p-1\)
2.若m=m1*m2 则
①若m1,m2有相同质因子,则\(\varphi(m)=m2\varphi(m1) (m2<=m1)\)
②若m1,m2互质,则\(\varphi(m)=\varphi(m1)\varphi(m2)\)
结论
①对于n,有\(n=\sum_{d|n}\varphi(d)\)
②引理:\(\varphi(n)=n\prod_{i=1}^k(1-\frac{1}{p_i})\)
证明：
①易得\(\sum_{d|m}\varphi(d)=\sum_{\frac{m}{d}|d}\varphi(d)=\sum_d\varphi(\frac{m}{d})\)
对于任意\(d|m,1\le a\le m\),设\(gcd(a,m)=d\),则\(gcd(\frac{a}{d},\frac{m}{d})=1\)