Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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 k2n.

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)=dnμ(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)=dnμ(d)F(n/d).

We have dnμ(d)F(n/d)=dnμ(d)e(n/d)f(e)=dne(n/d)μ(d)f(e)=end(n/e)μ(d)f(e)=enf(e)d(n/d)μ(d) Notice that d(n/e)μ(d)=0 unless n/e=1 and thus e=n. Consequently we get enf(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=dnμ(n/d)σ(d) and 1=dnμ(n/d)τ(d).

Exercises

  1. Find μ(12), μ(10!) and μ(105).
  2. Find the value of μ(n) for each integer n with 100n110.
  3. Use the Mobius inversion formula and the identity n=dnϕ(n/d) to show that ϕ(pt)=ptpt1 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.


This page titled 4.3: The Mobius Function and the Mobius Inversion Formula is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

Support Center

How can we help?