欧拉函数的两个性质

1.对
$n>1$

n>1，
$sumlimits_{gcd(n,i)=1}i=dfrac{ntimesvarphi(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}timesvarphi(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)timessum_{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)+dotsvarphi(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)=prodlimits_{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

证毕.