5
$\begingroup$

How do I evaluate

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

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

2 Answers 2

4

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 your 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} \cdot n$

4

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}$

  • 0
    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.2011-11-22