2
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ That is a nice proof! Thank you. Does my proof make sense? $\endgroup$
    – Mahidevran
    Nov 12 '15 at 17:14
  • 1
    $\begingroup$ @Mahidevran: your proof is perfectly fine, I just provided an alternative. $\endgroup$ Nov 12 '15 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.