Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What's the limit of the summation? –  Inceptio Mar 25 '13 at 9:00
    
@Inceptio $d|n$ –  agustin Mar 25 '13 at 9:12
2  
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

3 Answers 3

up vote 3 down vote accepted

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}$$

share|improve this answer
    
@anon It is my fatal mistake :( thanks to point out my mistake! –  tetori Mar 26 '13 at 1:42
1  
$(-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?

share|improve this answer

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.$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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