2
$\begingroup$

I would like to know if there is a closed form solution for

$$G(n)=\sum\limits_{d\mid n}(-1)^{\frac{n}{d}}\phi(d)$$

It seems quite likely there is since $$\sum\limits_{d\mid n}\phi(d)=n$$

But I cant see any general way to approach this nutshell. Any thoughts?

$\endgroup$
1
$\begingroup$

Let $n=2^km$ where $m$ is odd. For $(-1)^{\frac nd}$ to be odd, we need $d$ to be a multiple of $2^k$. So we could rewrite the sum as

$$\sum_{d\mid n}(-1)^{\frac nd}\phi(d)=\sum_{\substack{d\mid n\\2^k\nmid d}}\phi(d)-\sum_{\substack{d\mid n\\2^k\mid d}}\phi(d).$$

If $k=0$, the first sum in the RHS is empty and the result is simply $-n$. If $k\geq1$, $2^k\nmid d$ is equivalent to $d\mid\frac n2$. For the right sum we can write $d=2^ke$:

$$\sum_{d\mid n}(-1)^{\frac nd}\phi(d)=\sum_{d\mid\frac n2}\phi(d)-\sum_{e\mid m}\phi(2^ke).$$

As $e$ is odd every time, $\phi(2^ke)=2^{k-1}\phi(e)$. So $$\sum_{d\mid n}(-1)^{\frac nd}\phi(d)=\sum_{d\mid\frac n2}\phi(d)-2^{k-1}\sum_{e\mid m}\phi(e).$$

The first sum in the RHS is $\frac n2$, the second is $2^{k-1}m=\frac n2$. Hence their difference is $0$.

$\endgroup$
1
$\begingroup$

This appears to be $G(n)=0$ if $n$ is even $>0$, $G(n)= -n$ if $n$ is odd $>0$.

$\endgroup$
  • $\begingroup$ Wow... that is quite a simple form. $\endgroup$ – Elie Bergman Feb 28 '14 at 18:09

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.