Number Theory Euler totient function

Question

Prove that $$\sum_{d\mid n}(-1)^{n/d}\varphi(d)=\begin{cases}-n&2\nmid n\\0&2\mid n\end{cases}$$

I have came across the above question.

I have done the following:

• $n$ is odd then so is $n/d$ which would result $(-1)^{n/d}$ $=-1$

I am assuming you would have to use Gauss:

$$\sum_{d/n} φ(d) = n$$

$===>$ $$\sum_{d/n} (-1)^{n/d}φ(d) = -\sum_{d/n}φ(d)=-n$$

• $n$ is even then $n=2^{a}m$, where we can say $m$ is odd.

I am not sure what else to do from here. Any help would be appreciated.

Answer 1

One easy method is to notice that $$ a_n := \sum_{d\mid n}(-1)^{n/d}\varphi(d) \tag1 $$ is the Dirichlet convolution of two multiplicative sequences, $\,(-1)^n\,$ and $\, \varphi(n).\,$ The Dirichlet generating function series of the first is $$ f(s) := \sum_{n>0} (-1)^n/n^s = -1/1^s + 1/2^s - 1/3^s - \dots = -\frac{1-2/2^s}{1-1/2^s}\prod_{p>2}\frac1{1-1/p^s} \tag2 $$ and of the second is $$ g(s) := \sum_{n>0} \varphi(n)/n^s = 1/1^s + 1/2^s + 2/3^s + 2/4^s + \dots = \prod_{p} \frac{1-1/p^s}{1-p/p^s}. \tag3 $$ The Dirichlet convolution of the two sequences has Dirichlet generating function series $$ f(s)\,g(s) = -1/1^s - 3/3^s - 5/5^s - \dots = -\prod_{p>2} \frac1{1-p/p^s} \tag4 $$ because the $p=2$ factor in the second g.f. cancels the factor in the first.

Answer 2

If $n = 2^k$ for some $k \geq 1$, then:

\begin{align} \sum_{j = 0}^k (-1)^{2^{k-j}} \phi(2^j) &= \sum_{j=0}^{k-1} \phi(2^j) - \phi(2^k) \\ &= \sum_{j=0}^{k} \phi(2^j) - 2\phi(2^k) \\ &= 2^k - 2 \phi(2^k) \\ &= 2^k - 2\cdot 2^{k-1} = 0 \end{align}

Finally note that the sum is multiplicative.

Answer 3

Consider fractions $0<q\leq 1$ with denominator $n$, where $n$ is even. If $d|n$ then the number of such fractions with denominator $d$ when written in lowest terms is $\varphi(d)$.

Now if $n/d$ is even, what do you know about the numerators of these $\varphi(d)$ fractions when written with denominator $n$? Conversely if $n/d$ is odd what does that tell you about the numerators?

Your sum is just adding up the number of possible numerators where $n/d$ is even, and subtracting those that are odd.