>>793
包除原理を適用するだけでは？
>>794
φはEuler関数かな？
φは乗法的関数なので a = p_1^{a_1} * ... * p_k^{a_k} と素因数分解すると,
Σ[d|n] φ(n/d) = Π_{i=1}^{k} (Σ[d|p_i^{a_i}] φ(p_i^{a_i} / d))
が得られる.
Σ[d|p_i^{a_i}] φ(p_i^{a_i} / d) は帰納法的に p_i^{a_i} に等しいことが示せる.
よって, Σ[d|n] φ(n/d) = n である.