# Euler totient divisor sum [duplicate]

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

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

• 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. – user236182 Jan 28 '16 at 15:14
• 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. – Thomas Andrews Jan 28 '16 at 15:15