References: M�bius function - Mobius function, denoted μ(n); number of odd prime factors of square-free n
Möbius Function -- from Wolfram MathWorld
is the Mobius function.
Proof by multiplicative induction: It is true when n is prime, because .
Suppose . We will show that , where p is an arbitrary prime.
Consider only the square-free divisors of n, because when d has a square factor.
If p|n, the square-free divisors of np are the same as the square-free divisors of n, so .
If , the set of square-free divisors of np consists of all the square-free divisors of n together with each divisor multiplied by p.
Since (n, p) = 1, it follows from d|n that (d, p) = 1, and therefore . (The Mobius function is multiplicative: if (m, n) = 1.)
So the sum, above, is adding up a whole bunch of zeros, so . This completes the proof.