欧拉函数的两个性质

1.对$n>1$n>1，$\sum\limits_{gcd(n,i)=1}i=\dfrac{n\times\varphi(n)}{2}$gcd(n,i)=1∑​i=2n×φ(n)​

证明: $\because gcd(n,i)=gcd(n,n-i)$∵gcd(n,i)=gcd(n,n−i).因此互质的数以一对组成。

且$i+(n-i)=n$i+(n−i)=n.

每个互质的数的平均值为$\dfrac{n}{2}$2n​

所以原式$=\dfrac{n}{2}\times\varphi(n)$=2n​×φ(n)

证毕.

2.$f(n)=\sum_{d|n}\varphi(d)=n$f(n)=∑d∣n​φ(d)=n

证明：设$n,m$n,m互质$f(nm)=\sum_{d|nm}\varphi(d)=\sum_{d_1|n}\varphi(d_1)\times\sum_{d_2|m}\varphi(d_2)=f(n)\times f(m)$f(nm)=∑d∣nm​φ(d)=∑d1​∣n​φ(d1​)×∑d2​∣m​φ(d2​)=f(n)×f(m) 为积性函数。

因为（$\varphi(d)$φ(d)为积性函数，且$n,m$n,m互质,所以$d_1,d_2$d1​,d2​也是互质,所以可以分开写 )

对$n$n的某个因子$p^k$pk,$f(p^k)=\varphi(1)+\varphi(p)+\dots\varphi(p^k)$f(pk)=φ(1)+φ(p)+…φ(pk)

由$\varphi(p^i)=p^i-p^{i-1}(i>0)$φ(pi)=pi−pi−1(i>0)

$f(p^k)=1+p-p^0+p^2-p^1+\dots p^k-p^{k-1}=p^k$f(pk)=1+p−p0+p2−p1+…pk−pk−1=pk

因此$f(n)=\prod\limits_{i=1}^kf(p_i^{a_i})=p_1^{a_1}\times p_2^{a_2}\dots p_k^{a_k}=n$f(n)=i=1∏k​f(piai​​)=p1a1​​×p2a2​​…pkak​​=n

证毕.