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?

  • $\begingroup$ I don't get it: do you want to prove the sum is zero for even n and -n for odd n? $\endgroup$ – DonAntonio Sep 18 '13 at 16:26
  • $\begingroup$ @DonAntonio: yes $\endgroup$ – 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.

| cite | improve this answer | |

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.