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