Navigation   Home   Search   Site map

# document.write (document.title)

 Contact Graeme   Home   Email   Twitter
 Math Help > Number Theory > Theorems > Möbius function

The M�bius function is denoted μ(n), and defined as follows:

### Definition

μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
μ(n) = 0 if n is not square-free.

Square-free means not divisible by any square larger than 1.  The prime factors of square-free numbers are distinct.

### Sum for all d|n of μ(d) is 0, when n>1

 Sn = Σ d|n μ(d)  =  0

Proof by multiplicative induction:  Consider only the square-free divisors of n, because μ(d)=0 when d has a square factor.  It is true when n is prime, because μ(p)=-1, and u(1)=1; their sum is zero.

Suppose Sn=0 for n=m.  We will show that Sn=0 for n=mp, where p is an arbitrary prime.

If p|m then the square-free divisors of mp are the same as the square-free divisors of m, so Smp = Sm = 0.

If pm then the set of square-free divisors of mp consists of all the square-free divisors of m together with each divisor multiplied by p.  So,

 Smp = Σ d|m μ(d)+μ(pd)

Remembering that GCD(m,p)=1, it follows from d|m that GCD(d,p)=1, and therefore μ(pd) = −μ(d).  So the sum, above, is adding up a whole bunch of zeros, so Smp=0.

### M�bius Inversion Formula

If F(n) is an arithmetical function of n, and if

 G(n) = Σ d|n F(d)

then

 F(n) = Σ d|n μ(n/d) G(d)

and vice-versa.

Remarks

Before I begin the proof, I would like to make a few remarks about nested sums involving factors of n.  Understanding this will be key to understanding the proof that follows.

Consider all the possibilities for x and y, where x and y are selected according to the following method:

x is chosen to be a factor of n.  For example, if n=12, x will be one of {1,2,3,4,6,12}.

Then, after x is chosen, y is chosen to be a factor of "whatever is left over", namely n/x.  To take the example of n=12,

If x is 1, then y is one of the factors of 12/1, namely {1,2,3,4,6,12}
If x is 2, then y is one of the factors of 12/2, namely {1,2,3,6}
If x is 3, then y is one of the factors of 12/3, namely {1,2,4}
If x is 4, then y is one of the factors of 12/4, namely {1,3}
If x is 6, then y is one of the factors of 12/6, namely {1,2}
If x is 12, then y is one of the factors of 12/12, namely {1}.

Once all the choosing is done, we will have examined every possibility for x and y where x, y, and xy are all factors of n.  If we had chosen y first, and then picked x so that it divides "whatever is left over", we would have ended up with the same set of possibilities.  So a nested sum that runs through these possibilities of x and y can be rearranged any way we like, as long as the resulting sum runs through the same set of values in some order.

That's the key to understanding the proof that follows.

Proof:

Using the identity expressing G(n) as the sum of F(d) where d runs through the divisors of n,

 Σ d|n μ(n/d) G(d)  = Σ d|n μ(n/d) Σ e|d F(e)

Notice that the nested sum on the RHS runs through all the possibilities of μ(x) F(y) where x, y, and xy are factors of n.  Running through the same possibilities in a different order,

 Σ d|n μ(n/d) G(d)  = Σ e|n F(n/e) Σ d|e μ(d)

And since the sum for all d|n of μ(d) is 0 when n>1, the second sum is 1 only when e=1, so the RHS simplifies to F(n).

 Σ d|n μ(n/d) G(d)  =  F(n)

Conversely, using the second identity, expressing F(n) as the sum of μ(n/d) G(d) where d runs through the divisors of n,

 Σ d|n F(d)  = Σ d|n Σ e|d μ(d/e) G(e)

Rearranging the order the terms μ(x) F(y), (where x, y, and xy are factors of n), are summed,

 Σ d|n F(d)  = Σ e|n G(n/e) Σ d|e μ(d)

And, again, since the sum for all d|n of μ(d) is 0 when n>1, the RHS simplifies to G(n).

 Σ d|n F(d)  =  G(n)

### Application of the M�bius Inversion Formula

We have observed (and proved) already that the Sum of Totients of Divisors of n is n.  So if we let F be the totient function, and apply the M�bius Inversion Formula,

 G(n) = Σ d|n φ(d)

We see that G(n) is the identity function; that is, G(n)=n in this case.

If we apply the identity again, this time letting F be the identity function,

 G(n) = Σ d|n d

We see that G(n) is σ(n), the sum of divisors of n, denoted by the greek letter "sigma".

Starting from the M�bius function itself, and applying the M�bius inversion, we get the following new functions:

 U(n) = Σ d|n μ(d) —  the "unit" function that is 1 when n=1, and 0 otherwise
 1(n) = Σ d|n U(d) —  the "constant" function that is always 1
 τ(n) = Σ d|n 1(d) —  the "tau" function, the number divisors of n

The M�bius Inversion Formula can be used in either direction any number of times, forming a bi-infinite sequence of functions.

### Internet references

Wikipedia: Mobius inversion formula

Planet Math: Mobius Inversion Formula

### Related pages in this website

φ(n), the number of coprimes to n: Totient function

τ(n), the number of divisors of n: Divisors, Tau function

The webmaster and author of this Math Help site is Graeme McRae.