## Numbers, Mobius Function

### Mobius Function

If n is a positive integer,
the mobius function
μ(n),
named after MÃ¶bius
(biography),
is 0 if p2 divides n for some prime p,
1 if n is square free and contains an even number of prime factors,
and -1 if n is square free and contains an odd number of prime factors.
A literal interpretation gives μ(1) = 1.
Verify that μ(n) is a multiplicative function.
Given n > 1, consider the sum of μ(d) for all divisors d dividing n.
Split n into primes, and count
the squarefree factors having precisely k distinct primes.
If there are t total primes,
then there are t choose k such factors.
This is multiplied by μ, which is (-1)k.
To cover all the factors,
take the sum of t choose k times (-1)k as k runs from 0 to t.
Use the binomial theorem
to rewrite this sum as (1-1)t, or 0.

Oddly enough, the sum is still 0,
even if we consider the divisors d that are divisible by a base divisor b.
If a square divides b then the sum is 0, so assume b has l distinct primes.
Let k run from 0 to t-l,
as we consider divisors that have k distinct primes beyond b.
The l primes in b contribute 1 or -1; this is a constant.
The additional k factors introduce (-1)k.
Use the binomial theorem again to get (1-1)t-l, which is still 0.
Note that this breaks down if b = n.
That forces t-l = 0, and the binomial theorem doesn't work when the exponent is 0.