4.3: The Mobius Function and the Mobius Inversion Formula
( \newcommand{\kernel}{\mathrm{null}\,}\)
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\{ 1 if n=1; (−1)t if n=p1p2...pt where the pi are distinct primes; 0 otherwise.\right .\\)
Note that if n is divisible by a power of a prime higher than one then μ(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 k2∣n.
It is immediate (prove as exercise) that the prime-number factorization of a square-free integer contains only distinct primes.
Notice that μ(1)=1, μ(2)=−1, μ(3)=−1 and μ(4)=0.
We now prove that μ(n) is a multiplicative function.
The Mobius function μ(n) is multiplicative.
Let m and n be two relatively prime integers. We have to prove that μ(mn)=μ(m)μ(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 μ(mn)=0=μ(m)μ(n). What remains to prove that if m and n are square-free integers say m=p1p2...ps where p1,p2,...,ps are distinct primes and n=q1q2...qt where q1,q2,...,qt. Since (m,n)=1, then there are no common primes in the prime decomposition between m and n. Thus μ(m)=(−1)s,μ(n)=(−1)tand μ(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)=∑d∣nμ(d), then F(n) satisfies \[F(n)=\left\{ 1 if n=1; 0 if n>1.\right .\\]
For n=1, we have F(1)=μ(1)=1. Let us now find μ(pk) for any integer k>0. Notice that F(pk)=μ(1)+μ(p)+...+μ(pk)=1+(−1)+0+...+0=0 Thus by Theorem 36, for any integer n=pa11pa22...patt>1 we have, F(n)=F(pa11)F(pa22)...F(patt)=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)=∑d∣nμ(d)F(n/d).
We have ∑d∣nμ(d)F(n/d)=∑d∣nμ(d)∑e∣(n/d)f(e)=∑d∣n∑e∣(n/d)μ(d)f(e)=∑e∣n∑d∣(n/e)μ(d)f(e)=∑e∣nf(e)∑d∣(n/d)μ(d) Notice that ∑d∣(n/e)μ(d)=0 unless n/e=1 and thus e=n. Consequently we get ∑e∣nf(e)∑d∣(n/d)μ(d)=f(n).1=f(n).
A good example of a Mobius inversion formula would be the inversion of σ(n) and τ(n). These two functions are the summatory functions of f(n)=n and f(n)=1 respectively. Thus we get n=∑d∣nμ(n/d)σ(d) and 1=∑d∣nμ(n/d)τ(d).
Exercises
- Find μ(12), μ(10!) and μ(105).
- Find the value of μ(n) for each integer n with 100≤n≤110.
- Use the Mobius inversion formula and the identity n=∑d∣nϕ(n/d) to show that ϕ(pt)=pt−pt−1 where p is a prime and t is a positive integer.
Contributors and Attributions
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.