2
$\begingroup$

To prove this identity, $$\sum_{d \mid n}\phi(d)= n \qquad \text{for} \, n=1,2,3,\ldots$$ where $\phi (n)$ is the Eulers totient function, I tried this by breaking it into two parts, n is either an prime no or a composite no.

If the no is a prime no we have $\phi(1)$ + $\phi(n) = 1 + n - 1 = n $, however if n is composite we can write it in the form $n = p_1^{c_1} p_2^{c_2} \ldots p_k^{c_k}$,

So we will have $ \phi(1) + \phi(p_1) + \phi(p_2^2) + \ldots + \phi(p_1^{c_1}) $+ $\phi$(other prime terms with their combinations), how to solve this for composite no

$\endgroup$

marked as duplicate by Yai0Phah, lhf, Community Jan 28 '16 at 15:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ This has been posted here many times. One proof can be counting the number of fractions $\frac{n}{1},\frac{n}{2},\ldots,\frac{n}{n}$. Simplify the fractions and you'll get the result. $\endgroup$ – user236182 Jan 28 '16 at 15:14
  • $\begingroup$ Hint: Consider fractions of the form $\frac{a}{n}$ for $a=1,\dots,n$. Reduce them to $\frac{a'}{d}$ where $a',d$ relatively prime. $\endgroup$ – Thomas Andrews Jan 28 '16 at 15:15