LearnMathOnline

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\).

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).\]

\(\mu\) and Möbius Inversion Formula