Number Theory Home

## $$\mu$$ and Möbius Inversion Formula

German mathematician August Ferdinand Möbius introduced a number-theoretic function $$\mu$$ called Möbius $$\mu$$ function as follows: $$\mu(1)=1$$ and for any integer $$n>1$$ with the prime-power factorization $$n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$$, $\mu(n)= \begin{cases} 0&\text{ if } a_i\geq 2 \text{ for some } i\\ (-1)^k &\text{ if } a_i=1 \text{ for all } i. \end{cases}$

Alternately $$\mu(n)$$ can be defined using the square-freeness of $$n$$ for its prime factors: $\mu(n)=\left\lbrace \begin{array}{rl} 0&\text{ if $$n$$ is not square-free }\\ 1&\text{ if $$n$$ is a square-free product of an even number of primes }\\ -1&\text{ if $$n$$ is a square-free product of an odd number of primes. } \end{array} \right.$

Example. $$\mu(1)=1$$, $$\mu(2)=-1$$, $$\mu(3)=-1$$, $$\mu(4)=0$$, $$\mu(5)=-1$$, $$\mu(6)=1$$, and $$\mu(p)=-1$$ for any prime $$p$$.

Theorem. $$\mu$$ is a multiplicative function.

Proof. Let $$m$$ and $$n$$ be two relatively prime positive integers. We show $$\mu(mn)=\mu(m)\mu(n)$$. If $$m$$ or $$n$$ is not square-free, so is $$mn$$ and then $$\mu(m)\mu(n)=0=\mu(mn)$$. Suppose $$m$$ and $$n$$ are square-free where $$m=p_1p_2\cdots p_r$$ and $$n=q_1q_2\cdots q_s$$. Since $$\gcd(m,n)=1$$, $$p_i\neq q_j$$ for all $$i,j$$. Then $$mn=p_1p_2\cdots p_rq_1q_2\cdots q_s$$ and $$\mu(mn)=(-1)^{r+s}=(-1)^r(-1)^s=\mu(m)\mu(n)$$. ◼

Lemma. For any positive integer $$n$$, $\sum_{d\vert n} \mu(d)= \begin{cases}1& \text{ if }n=1\\ 0& \text{ if }n>1. \end{cases}$

Theorem.(Möbius Inversion Formula) Let $$f$$ and $$F$$ be two number-theoretic functions where $F(n)=\sum_{d\vert n} f(d).$ Then $f(n)=\sum_{d\vert n} \mu\left(\frac{n}{d}\right)F(d).$

Proof. First note that as $$d$$ runs over all the positive divisors of $$n$$, so does $$\frac{n}{d}$$. Then \begin{align*} \sum_{d\vert n} \mu\left(\frac{n}{d}\right)F(d) & =\sum_{d\vert n} \mu(d)F\left(\frac{n}{d}\right)\\ & =\sum_{d\vert n} \mu(d) \left(\sum_{c\vert \frac{n}{d}} f(c) \right)\\ & =\sum_{d\vert n} \sum_{c\vert \frac{n}{d}} \mu(d) f(c)\\ & =\sum_{c\vert n} \sum_{d\vert \frac{n}{c}} \mu(d) f(c) \text{ since } d\vert n, c\vert \frac{n}{d} \iff c\vert n, d\vert \frac{n}{c} \\ & =\sum_{c\vert n} f(c) \left( \sum_{d\vert \frac{n}{c}} \mu(d)\right). \end{align*} By the preceding lemma, $$\sum_{d\vert \frac{n}{c}} \mu(d)$$ is nonzero if and only if $$\frac{n}{c}=1$$, i.e., $$c=n$$. Thus \begin{align*} \sum_{d\vert n} \mu\left(\frac{n}{d}\right)F(d) & =\sum_{c\vert n} f(c) \left( \sum_{d\vert \frac{n}{c}} \mu(d)\right)\\ & =\sum_{\substack{c\vert n\\c=n}} f(c) \left( \sum_{d\vert 1=\frac{n}{c}} \mu(d)\right)\\ &= f(n) \cdot 1.◼ \end{align*}

Note that since $$\tau(n)=\sum_{d\vert n}1$$ and $$\sigma(n)=\sum_{d\vert n} d$$, by the Möbius Inversion Formula we have $1=\sum_{d\vert n} \mu\left(\frac{n}{d}\right)\tau(d) \text{ and } n=\sum_{d\vert n} \mu\left(\frac{n}{d}\right)\sigma(d).$

Last edited