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.

I'm trying to work through Ireland and Rosen's A Classical Introduction to Modern Number Theory as I've heard good things about it. This is Exercise 12 from Chapter 2. Here $\mu$ is the Moebius function, and $\phi$ the totient function.

Find formulas for $\sum_{d|n}\mu(d)\phi(d)$, $\sum_{d|n}\mu(d)^2\phi(d)^2$, and $\sum_{d|n}\mu(d)/\phi(d)$.


Playing around with the first sum, I know I can just sum over all square-free divisors $d$ of $n$, since otherwise $\mu(d)=0$. From that, if I let $\{p_1,\dots,p_m\}$ be the primes in the factorization of $n$, I believe that $\sum_{d|n}\mu(d)\phi(d)$ essentially subtracts $\phi(d)$ for all $d$ a single prime divisor of $n$, and then adds $\phi(d)$ for all $d=p_ip_j$ for $i\lt j$, then subtracts $\phi(d)$ for all $d=p_ip_jp_k$, $i\lt j\lt k$, etc., finally adding $(-1)^n\phi(d)$ for $d=p_1\cdots p_n$ and an extra $1$ for $\mu(1)\phi(1)=1$.

I think the same analysis for the third sum applies, except I would be adding or subtracting $1/\phi(d)$ in each summand above instead. For the second sum, I think it would be almost identical for the first sum, except I would be adding $\phi(d)^2$ for all possible combinations of different primes in the factorization of $n$.

I don't know how to express these sums in a nice way like I think the authors intend. I'd be grateful for suggestions on "nice" ways to express these, even though nice is a subjective term. Thanks.

share|improve this question

3 Answers 3

up vote 12 down vote accepted

Note that the terms $\mu(d) \phi(d)$, $\mu(d)^2 \phi(d)^2$, and $\mu(d)/ \phi(d)$ are all multiplicative. It therefore suffices to evaluate the sum for powers of a prime.

For example, for the first one,

$$ \sum_{d|p^\alpha} \mu(d) \phi(d) = \mu(1)\phi(1) + \mu(p) \phi(p) = 1-(p-1)=2-p. $$

Thus, writing $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ gives

$$ \sum_{d|n} \mu(d) \phi(d) = \prod_{j=1}^k (2-p_j). $$

share|improve this answer
    
@Andre, thank you very much for fixing the post. –  JavaMan Jul 29 '11 at 6:51
    
Thanks for the example DJC, I think it makes it more clear. Do you mind seeing if I did the others correctly? For the second, $$\sum_{d|p^\alpha}\mu(d)^2\phi(d)^2=1+(p-1)^2$$ so $\sum_{d|n}\mu(d)^2\phi(d)^2=\prod_{j=1}^k(1+(p_j-1)^2)$? And for the third, $$\sum_{d|n}\mu(d)/\phi(d)=\prod_{j=1}^k(1-1/(p_j-1))$$? –  yunone Jul 29 '11 at 19:52

A big hint for the first formula: keep in mind that $\phi(d)$ is multiplicative, so $\phi(p_1p_2)=\phi(p_1)\phi(p_2)$ for any two primes $p_1,p_2$; now consider the Inclusion-Exclusion theorem (or, equivalently, the expansion of the product $\Pi_i(1-x_i)$. A similar approach should work for the second formula, but you'll want to start with a different product since all the terms are positive...

share|improve this answer
    
Thanks for the tip! –  yunone Jul 29 '11 at 19:55

For the sake of having a complete answer:

For the second sum, $\displaystyle \sum_{d|p^\alpha}\mu(d)^2\phi(d)^2=1+(p-1)^2$ and so $$ \sum_{d|n}\mu(d)^2\phi(d)^2=\prod_{j=1}^k(1+(p_j-1)^2). $$ For the third, $\displaystyle \sum_{d|p^\alpha}\mu(d)/\phi(d)=1-\frac{1}{p-1}$, so $$ \sum_{d|n}\mu(d)/\phi(d)=\prod_{j=1}^k(1-1/(p_j-1)) $$ where the sums range over all primes in the factorization of $n$.

share|improve this answer
1  
They look good to me! –  JavaMan Jul 30 '11 at 0:17

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.