# For a positive integer $n$, prove that $\sum_{d|n}{(-1)^{\frac{n}{d}}\phi(d)}=0,\textit{if n is even and -n if n is odd.}$

For a positive integer $n$, prove that $$\sum_{d|n}{(-1)^{\frac{n}{d}}\phi(d)}= \begin{cases}0&\text{if n is even }\\ -n & \text{if n is odd.}\end{cases}$$

I totally have no idea how to solve this. I try to plug in some examples to see some connections, but i fail. Can anyone guide me?

• I don't get it: do you want to prove the sum is zero for even n and -n for odd n? – DonAntonio Sep 18 '13 at 16:26
• @DonAntonio: yes – Idonknow Sep 18 '13 at 16:28

Hint: The functions $(-1)^n$ and $\varphi(n)$ are multiplicative.
It follows by general theory that the function $f(n)$, where $$f(n)=\sum_{d|n} (-1)^{n/d}\varphi(d)$$ is multiplicative.
Thus you only need to deal with prime powers. We do a little of the work for $n=p^k$, where $p$ is an odd prime. Then all the $(-1)^{n/d}$ are $-1$. Forgetting about the $-1$ for a while, we want $$\varphi(1)+\varphi(p)+\cdots+\varphi(p^k).$$ This is $$1+(p-1)+(p-1)p+\cdots+(p-1)p^{k-1}.$$ The formula for the sum of a finite geometric progression will give you a nice simplified answer.
Remark: You may already know a formula for $\sum_{d|n}\varphi(d)$, it is typically done quite early. Then you can bypass the above computations, and obtain the result very quickly.