13
$\begingroup$

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.

3 Answers 3

14

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

  • 1
    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))$?2011-07-29
8

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

7

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

  • 1
    They look good to me!2011-07-30