Definition
μ(1) = 1. μ(p₁·p₂·…·pₖ) = (-1)^k for distinct primes. μ(p²·m) = 0.
Advertisement
Möbius inversion
g(n) = sum over d|n of f(d) ⟺ f(n) = sum over d|n of μ(n/d) · g(d). Elegant duality.
Advertisement
Counting coprime pairs
#{(a, b) : gcd(a, b) = 1, a, b ≤ N} = sum_d μ(d) · ⌊N/d⌋². Fast computation.
Sieve
Modified prime sieve computes μ(n) for all n ≤ N in O(N log log N).