# $\sum_{d|n}(-1)^{\frac nd}\phi(d)={}$?

how to find $$\sum_{d|n}(-1)^{\frac nd}\phi(d)=?$$

-
What's the limit of the summation? –  Inceptio Mar 25 '13 at 9:00
@Inceptio $d|n$ –  agustin Mar 25 '13 at 9:12
It was stated in a deleted answer that $(-1)^m$ is a multiplicative function. I think it is worth mentioning that it is not, in fact, multiplicative, so it does not suffice to check for prime powers. –  anon Mar 25 '13 at 10:04
In the title of this question, I extracted the question mark from the formula. The point is that an all-math-formula question makes it impossible to go to the question for those who have their MathJaX setting to "click to zoom". –  Marc van Leeuwen Mar 26 '13 at 9:22

We consider this sum for parity of $n$

If $n$ is odd, then $(-1)^{d}=-1$ for all $d|n$. (Because $d$ is also odd number.) So $$\sum_{d|n} (-1)^{n/d}\phi(d) = - \sum _{d|n} \phi(d)=-n$$

If $n$ is even, Let take $n=2^r N$, where $N$ is odd number and $r$ is nonnegative integer. Then this sum is represented following form: \begin{align*} \sum_{d|n} (-1)^{n/d}\phi(d) &= \sum_{i=0}^r \sum _{d|N} (-1)^{n/2^i d} \phi(2^i d) \\ &=\sum_{i=0}^{r-1} \sum_{d|N} (-1)^{n/2^i d} \phi(2^i d) + \sum_{d|N} (-1)^{N/d} \phi(2^r d)\\ &=-\sum_{i=0}^{r-1} \sum_{d|N} \phi(2^i)\phi(d) + \sum_{d|N}\phi(2^r)\phi(d)\\ &=-\sum_{i=0}^{r-1} \phi(2^i) \sum_{d|N} \phi(d) + \sum_{d|N}\phi(2^r)\phi(d)\\ &=-2^{r-1}N + 2^{r-1}N=0 \end{align*}

So $$\sum_{d|n} (-1)^{n/d}\phi(d) = \begin{cases} -n & \text{if n is odd} \\ 0 & \text{otherwise} \end{cases}$$

-
@anon It is my fatal mistake :( thanks to point out my mistake! –  tetori Mar 26 '13 at 1:42
$(-1)^{\frac{N}{d}}=-1$ not $1$ since $d,N$ is odd –  agustin May 11 '13 at 14:01

If $n$ is odd then $(-1)^{n/d}=-1$ for each $d\mid n$. Otherwise given $n=2^vm$ with $v\ge1$ and $m$ odd,

$$\sum_{d\mid n}(-1)^{n/d}f(d)=\left[\sum_{d\mid 2^{v-1}m}f(d)\right]-\left[\sum_{d\mid m}f(2^vd)\right].$$

Can you take it from here?

-

Hint: For $n \ge 1$, $$\sum_{d|n}\phi(d)=n$$

Let $S=\{1,2,3,\dots n\}$. For every positive divisor $d$ of $n$, let $S_d=\{m \in S |\gcd(m,n)=d\}$.

Then clearly, these sets $S_d$ are pairwise disjoint and their union is $S$.

Also $\gcd(m,n)=d \iff \gcd\left(\dfrac{m}{d},\dfrac{n}{d}\right)=1$. Hence the number of integers in the set $S_d$ is equal to the number of positive integers $\le\frac{n}{d}$ which are relatively prime to $\frac{n}{d}$ i.e equal to $\phi(\frac{n}{d})$.

Hence $n= \sum_{d|n} \phi\left(\dfrac{n}{d}\right)$. But as $d$ runs through all positive divisors of $n$, so does $\frac{n}{d}$. Hence

$$\sum_{d|n} \phi\left(\frac{n}{d}\right)=\sum_{d|n} \phi(d)=n.$$

-
This is useful for the computation at hand, but I think insight as to how to handle the $(-1)^{n/d}$ factor in OPs problem is necessary for a good answer here. Also please use \{ curly brackets \} for sets, as is standard - in number theory we often write $(a_1,\cdots,a_k)$ for the gcd of the numbers $a_i$ so it can easily be confused with this. –  anon Mar 25 '13 at 10:24
I will make sure of that. Thanks. –  Inceptio Mar 25 '13 at 10:38