# Nice formula for $\sum\limits_{d|n}(-1)^{n/d}\Phi(d)$?

How do I evaluate

$$\sum_{d|n}(-1)^{n/d}\Phi(d)?$$

$\Phi(d)$ is Euler's totient function. Thanks.

-

You can use the formula

$$\sum_{d | n} \Phi(d) = \sum_{d | n} \Phi\left(\frac{n}{d}\right)= n$$

And consider

$$\sum_{d | n} \Phi\left(\frac{n}{d}\right) + \sum_{d | n} (-1)^{d} \Phi\left(\frac{n}{d}\right) = \sum_{d | n} (1+(-1)^{d}) \, \Phi\left(\frac{n}{d}\right) = 2 \sum_{2d | n} \Phi\left(\frac{n}{2d}\right)$$

If $n$ is odd, then this is equal to $0$. Otherwise, you get

$$2 \sum_{2d | n} \Phi\left(\frac{n}{2d}\right) = 2 \sum_{d | n/2} \Phi\left(\frac{n/2}{d}\right) = n$$

So you sum is $-n$ if $n$ is odd, and $0$ otherwise. You can sum it up as

$$\sum_{d | n} (-1)^{n/d} \Phi\left(d\right) = \sum_{d | n} (-1)^{d} \Phi\left(\frac{n}{d}\right) = \frac{(-1)^n-1}{2} . n$$

-
Thanks a lot! =D –  Eric Nov 22 '11 at 14:02

We are performing Dirichlet convolution on $(-1)^k$ and $\Phi(k)$. The corresponding Dirichlet generating functions of these two sequences are

\begin{align*}\frac{\zeta(s-1)}{\zeta(s)}&=\sum_{k=1}^\infty \frac{\Phi(k)}{k^s}\\(2^{1-s}-1)\zeta(s)&=\sum_{k=1}^\infty \frac{(-1)^k}{k^s}\end{align*}

where $\zeta(s)$ is Riemann's function.

The product of these two generating functions is the generating function of the convolution; we thus seek the Dirichlet series for $(2^{1-s}-1)\zeta(s-1)$.

We have the Dirichlet $\lambda$ function

$$\lambda(s)=\sum_{k=1}^\infty \frac{1-(-1)^k}{2k^s}=(1-2^{-s})\zeta(s)$$

and we see that our generating function is precisely $-\lambda(s-1)$. Thus, the Dirichlet convolution of $\Phi(k)$ and $(-1)^k$ is

$$-\dfrac{k(1-(-1)^k)}{2}=\begin{cases}-k&\text{odd }k\\0&\text{even }k\end{cases}$$

-
Thank you very much, though I have to admit, I do not know Dirichlet convolution a lot. –  Eric Nov 22 '11 at 14:02
Have a look at the wiki article I linked to. You can ask questions here if there's anything you don't understand about them. –  Ｊ. Ｍ. Nov 22 '11 at 14:42