Show that $\sum_{m|n}\phi(m)=n$

Show that $$\sum_{m|n,\; m>0}\phi(m)=n$$ where $\phi$ is Euler's totient function.

What I did:

There are $n-\phi(n)$ elements in the set $S_1=\{m:m|n,\;0<m<n\}$. This set is nonempty if $n>1$ since $1$ is in the set. Since it is a finite set of integers, there exists a maximum, call it $n_1$. Then there are $n-\phi(n)-\phi(n_1)$ elements in the set $S_2=\{m:m|n,\;0<m<n_1\}$. Since we can continue this process until we get the empty set, then we arrive to the conclusion that $n-\sum_{m|n}\phi(m)=0$.

Is this proof correct?

The book I took it from suggests using the following facts: $\phi(m)$ counts the number of generators of the cyclic group $C_m$, that every element of $C_n$ generates a subgroup of $C_n$, and that every subgroup of $C_n$ is isomorphic to $C_m$ for some $m|n$.

• a function $f$ on the natural numbers is called "multiplicative" if, whenever $\gcd(a,b) = 1,$ we also get $f(ab) = f(a) f(b).$ The Euler totient $\phi(n)$ is multiplicative. A multiplicative function is completely determined by the values it takes on primes and prime powers. Finally, if $f$ is multiplicative, so is $g(n) = \sum_{m|n} f(m)$ Jul 28 '17 at 23:25
• For reference, this question defines the totient function for the first time and then asks this question subsequently, without trying to show its properties. Jul 28 '17 at 23:28
• @George I'm afraid your proof won't work. The reason is that not all numbers less than n that aren't relatively prime to n actually divide n. Take 18 and 16. They're not relatively prime. But 16 doesn't divide 18...
– user403337
Jul 29 '17 at 0:43
• The proof in silverman uses the fact that phi is multiplicative; and I believe this is essentially the Chinese remainder theorem. ..
– user403337
Jul 29 '17 at 1:39

The intended solution seems to be this: we have $n$ elements in $C_n$. Now for each element $a$ of $C_n$, consider the subgroup $\langle a\rangle$, the cyclic subgroup generated by $a$. This is isomorphic to some $C_m$ for some $m\mid n$. Now group the elements by this $m$. Note that there are $\varphi(m)$ elements that generate $C_m$. Thus, summing across the $m$ gives the right hand side. On the other hand, we started with $n$ elements so this gives the left hand side.

This is the algebraic version of this combinatorial proof: write down the fractions $1/n, 2/n, \dots, n/n$ and simplify them. Then, $\varphi(m)$ of the fractions will have denominator $m$, but we have $n$ fractions, so we have the desired identity.

$\phi(n)$ is the number of integers relatively prime to n. So $\phi(n) - n$ is the number of integers that are not relatively prime to $n$, but not necessary divisors of $n$. But in your definition of $S_1$ you are only counting divisors of $n$.

For the proof using group theory take a look at this:

Difficulty understanding the proof that $n=\sum_{d|n} \phi(d)$

Following Silverman, first let $F (n)=\sum_{d|n}\phi (d)$ and prove $F (p^n)=p^n$(use $\phi (p^n)=p^n-p^{n-1}$ to get a "telescoping" sum). Then use the multiplicative property of $\phi$ to get (easily) that F is multiplicative. Then write $n={p_1}^{n_1}{p_2}^{n_2}\dots {p_k}^{n_k}$ and finish the proof...

Or you could use the method of Gauss, which is probably the slickest I've seen https://en.m.wikipedia.org/wiki/Euler%27s_totient_function. See "divisor sum"...