let $\phi$ denote the Euler's function. Prove the identity $\Sigma_{d|n}\phi(d) = n$, where the sum is extended over all the divisors $d$ of $n$.
attempt: Suppose $Z$ is a cyclic group of order $n$. Then by theorem, every subgroup of a cyclic group is cyclic. So every subgroup of Z is cyclic. And by another theorem, for each positive integer $q$ dividing $n$ , there is a unique subgroup of Z of order $q$, for each $d|n$. Then each $q \in Z$ is contained in some cyclic subgroup. The number of elements of Z of order $d$ is $\phi(d)$ . Thus , in the cyclic group Z there are $\phi(d)$ elements of order $d|n$ . Since by Lagrange's theorem, every element has order that divides $n$ , then the number of elements in Z is $\Sigma_{d|n}\phi(d) = n$.
Can someone please verify this? Any feedback would really help or better approach. Thank you!
Best Answer
If $f$ is a multiplicative function, $$ F(n)=\sum_{d\mid n}f(d) $$ is a multiplicative function, too (it can be regarded as a simple consequence of the Chinese remainder theorem). If we take $f=\phi$ and $n=p^k$, we have: $$ \sum_{d\mid n}\phi(d) = \sum_{j=0}^{k}\phi(p^j) = 1+(p-1)\sum_{j=1}^{k}p^{j-1} = p^k, $$ hence for every $n$, $$ \sum_{d\mid n}\phi(d) = n$$ holds.