$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.3: The Mobius Function and the Mobius Inversion Formula

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

We start by defining the Mobius function which investigates integers in terms of their prime decomposition. We then determine the Mobius inversion formula which determines the values of the a function $$f$$ at a given integer in terms of its summatory function.

$$\mu(n)=\left\{\begin{array}{lcr} \ 1 \ \ \mbox{if}\ \ n=1;\\ \ (-1)^t \ \ \mbox{if}\ \ n=p_1p_2...p_t \ \ \mbox{where the}\ \ p_i \ \ \mbox{are distinct primes};\\ \ 0 \ \ \mbox{ otherwise}.\\ \end{array}\right .\$$

Note that if $$n$$ is divisible by a power of a prime higher than one then $$\mu(n)=0$$.

In connection with the above definition, we have the following

An integer $$n$$ is said to be square-free, if no square divides it, i.e. if there does not exist an integer $$k$$ such that $$k^2\mid n$$.

It is immediate (prove as exercise) that the prime-number factorization of a square-free integer contains only distinct primes.

Notice that $$\mu(1)=1$$, $$\mu(2)=-1$$, $$\mu(3)=-1$$ and $$\mu(4)=0$$.

We now prove that $$\mu(n)$$ is a multiplicative function.

The Mobius function $$\mu(n)$$ is multiplicative.

Let $$m$$ and $$n$$ be two relatively prime integers. We have to prove that $\mu(mn)=\mu(m)\mu(n).$ If $$m=n=1$$, then the equality holds. Also, without loss of generality, if $$m=1$$, then the equality is also obvious. Now suppose that $$m$$ or $$n$$ is divisible by a power of prime higher than 1, then $\mu(mn)=0=\mu(m)\mu(n).$ What remains to prove that if $$m$$ and $$n$$ are square-free integers say $$m=p_1p_2...p_s$$ where $$p_1,p_2,...,p_s$$ are distinct primes and $$n=q_1q_2...q_t$$ where $$q_1,q_2,...,q_t$$. Since $$(m,n)=1$$, then there are no common primes in the prime decomposition between $$m$$ and $$n$$. Thus $\mu(m)=(-1)^s, \mu(n)=(-1)^t \mbox{and} \ \ \mu(mn)=(-1)^{s+t}.$

In the following theorem, we prove that the summatory function of the Mobius function takes only the values $$0$$ or $$1$$.

Let $$F(n)=\sum_{d\mid n}\mu(d)$$, then $$F(n)$$ satisfies $F(n)=\left\{\begin{array}{lcr} \ 1 \ \ \mbox{if}\ \ n=1;\\ \ 0 \ \ \mbox{if}\ \ n>1.\\ \end{array}\right .\$

For $$n=1$$, we have $$F(1)=\mu(1)=1$$. Let us now find $$\mu(p^k)$$ for any integer $$k>0$$. Notice that $F(p^k)=\mu(1)+\mu(p)+...+\mu(p^k)=1+(-1)+0+...+0=0$ Thus by Theorem 36, for any integer $$n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}>1$$ we have, $F(n)=F(p_1^{a_1})F(p_2^{a_2})...F(p_t^{a_t})=0$

We now define the Mobius inversion formula. The Mobius inversion formula expresses the values of $$f$$ in terms of its summatory function of $$f$$.

Suppose that $$f$$ is an arithmetic function and suppose that $$F$$ is its summatory function, then for all positive integers $$n$$ we have $f(n)=\sum_{d\mid n}\mu(d)F(n/d).$

We have \begin{aligned} \sum_{d\mid n}\mu(d)F(n/d)&=&\sum_{d\mid n}\mu(d)\sum_{e\mid (n/d)}f(e)\\ &=& \sum_{d\mid n}\sum_{e\mid (n/d)}\mu(d)f(e)\\&=&\sum_{e\mid n}\sum_{d\mid (n/e)}\mu(d)f(e)\\&=&\sum_{e\mid n}f(e)\sum_{d\mid (n/d)}\mu(d)\\\end{aligned} Notice that $$\sum_{d\mid (n/e)}\mu(d)=0$$ unless $$n/e=1$$ and thus $$e=n$$. Consequently we get $\sum_{e\mid n}f(e)\sum_{d\mid (n/d)}\mu(d)=f(n).1=f(n).$

A good example of a Mobius inversion formula would be the inversion of $$\sigma(n)$$ and $$\tau(n)$$. These two functions are the summatory functions of $$f(n)=n$$ and $$f(n)=1$$ respectively. Thus we get $n=\sum_{d\mid n}\mu(n/d)\sigma(d)$ and $1=\sum_{d\mid n}\mu(n/d)\tau(d).$

Exercises

1. Find $$\mu(12)$$, $$\mu(10!)$$ and $$\mu(105)$$.

2. Find the value of $$\mu(n)$$ for each integer $$n$$ with $$100\leq n\leq 110$$.

3. Use the Mobius inversion formula and the identity $$n=\sum_{d\mid n}\phi(n/d)$$ to show that $$\phi(p^t)=p^t-p^{t-1}$$ where $$p$$ is a prime and $$t$$ is a positive integer.

### Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.