I've already proved that the above sum is $-n$ when $n$ is odd, but I'm having trouble proving the case for when $n$ is even.

So far I've done the following work:

Since $n$ is even, there exists $t \geq 0$ such that $n = 2^{t}n_{0}$, for $n_{0}$ odd.


\begin{align*} \sum_{d \mid n} (-1)^{\frac{n}{d}} \varphi(d) &= \sum_{k=0}^{t} \sum_{d \mid n_{0}} (-1)^{\frac{n}{2^{k}d}} \varphi (2^{k}d)\\ &= \sum_{k=0}^{t-1} \left(\sum_{d\mid n_{0}} (-1)^{\frac{n}{2^{k}d}} \varphi(2^{k}d) \right)+ \sum_{d \mid n_{0}} (-1)^{\frac{n}{2^{t}d}} \varphi(2^{t}d)\\ &= \sum_{k=0}^{t-1} \left(\sum_{d\mid n_{0}} (-1)^{\frac{n}{2^{k}d}} \varphi(2^{k}d) \right)+ \sum_{d \mid n_{0}} (-1)^{\frac{n_{0}}{d}} \varphi(2^{t}d)\\ &= \sum_{k=0}^{t-1} \left(\sum_{d\mid n_{0}} (-1)^{\frac{n}{2^{k}d}}\varphi(2^{k}d) \right) - \sum_{d \mid n_{0}} \varphi(2^{t}d). \end{align*}

From here, if I can eliminate the $(-1)^{\frac{n}{2^{k}d}}$ term from the first sum, then the result follows easily since $(2^{t},d)=1$ for all $t$. I can't seem to find a way to prove that $(-1)^{\frac{n}{2^{k}d}}$ is always positive, however. If anyone has any ideas or could assist in any way (Am I even on the right track?) then it would be greatly appreciated, thanks!

  • 2
    $\begingroup$ How can it be $0$ for odd $n$? For odd $n$, $\frac nd$ is always odd, so the sign is always negative? $\endgroup$ – joriki Feb 12 '20 at 0:04
  • $\begingroup$ @joriki Thanks for pointing that out, I meant $-n$. I'll fix it. $\endgroup$ – BalsamicVinegar Feb 12 '20 at 4:05
  • 1
    $\begingroup$ $n = 2^{t}n_{0}$, $\frac{n}{2^{k}d}= \frac{2^tn_0}{2^k d} =2^{t-k} \frac{n_0}{d}$, but in the sum we have $0 \le k \le t-1$ so we have that $2| \frac{n}{2^kd}$. $\endgroup$ – Mason Feb 12 '20 at 7:58

I think the way you have written is fine but if your goal was to organize this as the positive terms and the negative terms you can split this exactly this way.

Note that $$\sum_{d|n} f(n/d)g(d)=\sum_{d|n}g(n/d)f(d)=\sum_{ab=n} f(a)g(b)$$

So we rewrite this with a $(-1)^d$ instead of $(-1)^{n/d}$

$$\sum_{d|2^kn_0} (-1)^{2^kn_0/d} \phi(d)=\sum_{d|2^kn_0} (-1)^d \phi(2^kn_0/d)$$

$$=\color{blue}{\sum_{d|2^kn_0, \\ (-1)^d=1} (-1)^d \phi(2^k n_0/d)} + \color{red}{\sum_{d|2^kn_0, \\ (-1)^d=-1} (-1)^d \phi(2^k n_0/d)}$$

$$=\color{blue}{\sum_{d|2^kn_0} \phi(2^kn_0/d)-\sum_{d|n_0} \phi(2^kn_0/d)}-\color{red}{\sum_{d|n_0} \phi(2^kn_0/d)}$$

$$=\sum_{d|2^kn_0} \phi(2^k n_0/d)-2\sum_{d|n_0} \phi(2^k n_0/d)$$

In the the case that $k>0, m\in2\mathbb{N}+1$ we have $\phi(2^km)=2^{k-1}\phi(m)$ $$=\sum_{d|2^kn_0} \phi(2^k n_0/d)-2^k\sum_{d|n_0} \phi( n_0/d)$$ And because $\sum_{d|x} \phi(x/d)=x,$ $$=2^kn_0-2^kn_0=0$$


We can work with formal Dirichlet series and define a coefficient extractor

$$[n^{-s}] \sum_{n\ge 1} a(n)/n^s = a(n).$$

This is an analogue of formal power series. We then have from $\sum_{d|n} \varphi(d) = n$ that

$$A(s) = \sum_{n\ge 1} \varphi(n)/n^s = \frac{\zeta(s-1)}{\zeta(s)}.$$

We also have

$$B(s) = \sum_{n\ge 1} (-1)^n/n^s = (2^{1-s} - 1 ) \zeta(s).$$

The desired quantity is then given by

$$[n^{-s}] A(s) B(s) = [n^{-s}] (2^{1-s}-1) \zeta(s-1).$$

We then have

$$[(2m+1)^{-s}] (2^{1-s}-1) \zeta(s-1) \\ = [(2m+1)^{-s}] (-\zeta(s-1)) = - (2m+1)$$


$$[(2m)^{-s}] (2^{1-s}-1) \zeta(s-1) \\ = [m^{-s}] 2 \zeta(s-1) - [(2m)^{-s}] \zeta(s-1) = 2m - 2m = 0.$$

All is as claimed.


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.