# Number Theory Euler totient function [duplicate]

This question already has an answer here:

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.

## marked as duplicate by Lord Shark the Unknown, José Carlos Santos, Community♦Nov 21 '18 at 23:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Here $\phi$ is Euler totient function? What does "use Gauss" mean? I assume you are referring to the result that $\sum_{d\mid n}(-1)^{n/d}\phi(d) = n$? – JavaMan Nov 16 '18 at 3:12
• @JavaMan yes that is correct. I should add that in my question. – Hidaw Nov 16 '18 at 3:13
• Consider $d=2^{m_1} m_2$ where $m_1\geq 0$, $m_2$ is odd. – i707107 Nov 16 '18 at 3:49
• @mathlove yes it is! I did not find that. My apologizes. I can no longer delete it since i have received an answer. – Hidaw Nov 16 '18 at 3:54

## 3 Answers

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.

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.

Consider fractions $$0 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.