4.3: The Mobius Function and the Mobius Inversion Formula

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.