suppose $\omega(n)$ denote the number of distinct prime factors of n

Suppose $\omega(n)$ denote the number of distinct prime factors of n. Prove that$$|\mu(n)|=\sum_{d|n}\mu(d)*2^{\omega(n/d)}$$ Can any one give me some hints about this problem? Is $\mu(n)$ a multiplicative function?

Any help would be appreciated.

• $\mu$ is definitely multiplicative. Consider $\mu(m), \mu(n)$. Look at cases where if either $m$ or $n$ is not square free, then $mn$ is not square free which means $\mu(mn)=0$. Then suppose both are square free....then $mn$ is also square free. Now consider their prime decompositions since they are not square free. This should be enough evidence to tell you it is a multiplicative function. – Lalaloopsy Jul 23 '14 at 4:21
• thank you! I get the idea now. – Jestem Jul 23 '14 at 4:37

This problem can be done in three steps. Put $$g(n) = \sum_{d|n} \mu(d) \times 2^{\omega(n/d)}.$$

The first step is to note that since $\mu(n)$ and $2^{\omega(n)}$ are both multiplicative so is $g(n).$

The second step is to apply Moebius inversion to obtain $$2^{\omega(n)} = \sum_{d|n} g(n).$$

The third is to calculate $g(n)$ from this equation. We start with $n=1$ $$g(1) = 2^{\omega(1)} = 1$$ and continue with $n=p$ where $p$ is a prime $$g(1) + g(p) = 2^{\omega(p)} = 2\quad\text{thus}\quad g(p) = 1.$$

Next is $n=p^2$ which gives $$g(1) + g(p) + g(p^2) = 2$$ so $$g(p^2) = 0.$$

Continuing we have by induction that $g(p^v) = 0$ for $v\ge 2.$ But since $g$ is multiplicative this means that $g(n)$ is zero if $n$ is not squarefree and one otherwise, which is precisely the defintion of $|\mu(n)|$ so that $$g(n) = |\mu(n)|$$ which was to be shown.

• By Moebius Inversion, the second step might be $$2^{\omega(n)} = \sum_{d|n} g(d).$$ – Jestem Jul 24 '14 at 5:11