
The M�bius function is denoted μ(n), and defined as follows:
μ(n) = 1 if n is a squarefree positive integer with an even number of
prime factors.
μ(n) = −1 if n is a squarefree positive integer with an odd number of prime
factors.
μ(n) = 0 if n is not squarefree.
Squarefree means not divisible by any square larger than 1. The prime factors of squarefree numbers are distinct.
S_{n} =
Σ
dnμ(d) = 0
Proof by multiplicative induction: Consider only the squarefree 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 S_{n}=0 for n=m. We will show that S_{n}=0 for n=mp, where p is an arbitrary prime.
If pm then the squarefree divisors of mp are the same as the squarefree divisors of m, so S_{mp} = S_{m} = 0.
If pm then the set of squarefree divisors of mp consists of all the squarefree divisors of m together with each divisor multiplied by p. So,
S_{mp} =
Σ
dmμ(d)+μ(pd)
Remembering that GCD(m,p)=1, it follows from dm that GCD(d,p)=1, and therefore μ(pd) = −μ(d). So the sum, above, is adding up a whole bunch of zeros, so S_{mp}=0.
If F(n) is an arithmetical function of n, and if
G(n) =
Σ
dnF(d)
then
F(n) =
Σ
dnμ(n/d) G(d)
and viceversa.
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,
Σ
dnμ(n/d) G(d) =
Σ
dnμ(n/d)
Σ
edF(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,
Σ
dnμ(n/d) G(d) =
Σ
enF(n/e)
Σ
deμ(d)
And since the sum for all dn of μ(d) is 0 when n>1, the second sum is 1 only when e=1, so the RHS simplifies to F(n).
Σ
dnμ(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,
Σ
dnF(d) =
Σ
dnΣ
edμ(d/e) G(e)
Rearranging the order the terms μ(x) F(y), (where x, y, and xy are factors of n), are summed,
Σ
dnF(d) =
Σ
enG(n/e)
Σ
deμ(d)
And, again, since the sum for all dn of μ(d) is 0 when n>1, the RHS simplifies to G(n).
Σ
dnF(d) = G(n)
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) =
Σ
dnφ(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) =
Σ
dnd
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) =
Σ
dnμ(d)
— the "unit" function that is 1 when n=1, and 0 otherwise
1(n) =
Σ
dnU(d)
— the "constant" function that is always 1
τ(n) =
Σ
dn1(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 biinfinite sequence of functions.
Wikipedia: Mobius inversion formula
Planet Math: Mobius Inversion Formula
φ(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.