4
$\begingroup$

I'm learning about the Möbius Inversion Formula but I'm stuck on an exercise which involves the Möbius function.

Let $n\in\mathbb{Z}$ with $n>0$ and let $\omega(n)$ denote the number of distinct prime numbers dividing n. Prove that

$$\sum_{d|n,d>0} |\mu(d)| = 2^{\omega(n)}$$

I can see that $\sum|\mu(d)|$ is divisible by $2$ but I don't know how to relate it to $\omega(n)$. Could someone give me a hint in the right direction on how to approach this proof?

$\endgroup$

2 Answers 2

2
$\begingroup$

Hint: Suppose that $P = \{p_1,\ldots,p_{\omega(n)}\}$ are the distinct primes divising $n$. Then $\mu(d) \neq 0$ (and so $|\mu(d)| = 1$) for $d|n$ only if $d$ is a product of a subset of $P$.

$\endgroup$
2
  • $\begingroup$ Oh, so I could just use the cardinality of the power set $|\mathbb{P}(P)| = 2^{\omega(n)}$? $\endgroup$ Mar 19, 2015 at 1:42
  • $\begingroup$ Yes, that's the idea. $\endgroup$ Mar 19, 2015 at 1:43
0
$\begingroup$

(Brutal solution: )

$|\mu(n)|$ is also a Arithmetic function, so is $f(n) = \sum_{d|n}|\mu(d)|$.

Since $f(p^n) = 2$

Then $f(p^aq^b \dots) = f(p^a)f(q^b) \dots = 2^{\omega(n)}$

$\endgroup$

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.