Showing $\sum_{d\mid n} \mu(d)\tau(n/d)=1$ and $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$

Question

Need some help on this question from Victor Shoup

Let $\tau(n)$ be the number of positive divisors of $n$. Show that:

• $\sum_{d\mid n} \mu(d)\tau(n/d)=1$;
• $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$, where $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of $n$.

I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove this Question.

Answer 1

Using the fact that both $\mu$ and $\tau$ are multiplicative for the first one we get from first principles the value

$$\tau(n) \prod_{q=1}^r \left(1+(-1)\times\frac{e_q}{e_q+1}\right)$$

which simplifies to

$$\tau(n) \prod_{q=1}^r \frac{1}{e_q+1} = 1.$$

For the second one we may write

$$\prod_{q=1}^r (1+(-1)\times 2) = (-1)^r.$$

Here we have used that for a subset $S$ of the set of prime factors $P$ corresponding to a squarefree divisor $d$ of $n$ we get $\mu(d) = (-1)^{|S|}$ and $\tau(n/d) = \tau(n) \prod_{p_q\in S} \frac{e_q}{e_q+1}.$

Answer 2

1) $τ(n)= \sum_{d|n} 1$ => According to the Moebius Inversion Formula $\sum_{d|n} μ(d)τ(n/d) = 1$

2) If d has a squared prime factor, then μ(d)=0 => $\sum_{d|n} μ(d)τ(d) = \sum_{d|rad(n)} μ(d)τ(d)$. If the number of prime factors of n is even, then μ(rad(n)/d)= μ(d). If it is odd, then μ(rad(n)/d)= -μ(d) => $\sum_{d|n} μ(d)τ(d) = \sum_{d|rad(n)} μ(d)τ(d) = (-1)^r \sum_{d|rad(n)} μ(rad(n)/d)τ(d)= (-1)^r \sum_{d|rad(n)} μ(d)τ(rad(n)/d)=(-1)^r.$