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.

  • 1
    $\begingroup$ $\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. $\endgroup$ – Lalaloopsy Jul 23 '14 at 4:21
  • $\begingroup$ thank you! I get the idea now. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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