大意是：求证
[sum_{d|n} varphi(d)=n
]
定理①：
[sum_{z|mn}varphi(z)=sum_{x|m}varphi(x)sum_{y|m}varphi(y)[gcd(m,n)=1]
]
有(sum)在里面不太好看，设(m)的所有因数为:
(a_1,a_2...a_k),
(n)的所有因数为:
(b_1,b_2...b_l)
乘起来后易得：
[sumlimits_{i=1}^ksumlimits_{j=1}^lvarphi(a_i)varphi(b_j)=sum_{x|m}varphi(x)sum_{y|m}varphi(y)=sum_{z|mn}varphi(z)
]
所以该结论成立。
定理②：
[varphi(a^b)=a^b-a^{b-1}
]
其中(a)是质数。
在([1,a^b])中，只有(a)的倍数与(a^p)不互质共有(a^{b-1})个
所以该结论成立。
运用该结论，我们知道
(sum_{d|p^m}varphi(d)=varphi(1)+varphi(p)+...+varphi(p^m))((p in mathbb{P}))
(=1+sumlimits_{i=1}^m(p^i-p^{i-1}))
(=1+(p-1)(1+sumlimits_{i=1}^{m-1}p^i))
(=1+sumlimits_{i=1}^mp^i-(1+sumlimits_{i=1}^{m-1}p^i)=p^m)
所以：
[sum_{d|n} varphi(d)=prod_{i=1}^msum_{d|p_i^{c_i}}d=prod_{i=1}^mp_i^{c_i}=n
]
(SO) :
[sum_{d|n} varphi(d)=n
]
完结撒花~~~