3
$\begingroup$

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.

$\endgroup$

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.

  • 1
    $\begingroup$ 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$? $\endgroup$ – JavaMan Nov 16 '18 at 3:12
  • $\begingroup$ @JavaMan yes that is correct. I should add that in my question. $\endgroup$ – Hidaw Nov 16 '18 at 3:13
  • 1
    $\begingroup$ Consider $d=2^{m_1} m_2$ where $m_1\geq 0$, $m_2$ is odd. $\endgroup$ – i707107 Nov 16 '18 at 3:49
  • $\begingroup$ @mathlove yes it is! I did not find that. My apologizes. I can no longer delete it since i have received an answer. $\endgroup$ – Hidaw Nov 16 '18 at 3:54
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.