Arithmetic functions · Definition

Möbius inversion formula

elementary number theoryarithmetic functions

Before you start you need to know

Many arithmetic functions are defined as sums over divisors, and sometimes one needs to undo that operation. This formula does so explicitly.

Definition

Formula that recovers an arithmetic function \(f\) from its sum over divisors, using the Möbius function \(\mu\).

\[f(n)=\sum_{d\mid n}\mu(d)\,g\!\left(\frac{n}{d}\right)\]

If \(g\) is the sum of \(f\) over the divisors of each \(n\), inversion recovers \(f\) as a sum of \(g\) evaluated at quotients \(n/d\), weighted by \(\mu(d)\). The two relations are equivalent thanks to the identity \(\sum_{d\mid n}\mu(d)\), which equals 1 when \(n=1\) and 0 otherwise.

Take \(g(n)=n\), whose inversion gives Euler's \(f=\varphi\). For \(n=6\), the divisors \(d=1,2,3,6\) give \(\mu(d)=1,-1,-1,1\) and quotients \(6,3,2,1\), so \(\varphi(6)=6-3-2+1=2\).

A common mistake is mismatching the arguments, using \(g(d)\) instead of \(g(n/d)\) or summing over the multiples of \(n\) rather than its divisors. With \(n=6\) this gives results that do not match \(\varphi(6)=2\).

Think about it

Why does the inversion formula need the identity \(\sum_{d\mid n}\mu(d)\)?

Because that sum equals 1 when \(n=1\) and 0 otherwise, which lets us isolate \(f\) from \(g\).

Exercises 10

  1. Which arithmetic function appears as the coefficient in the Möbius inversion formula?
  2. What is the correct way to invert \(g(n)=\sum_{d\mid n}f(d)\)?
  3. Over which set is the sum taken in \(g(n)=\sum_{d\mid n}f(d)\)?
  4. If \(g(n)=\sum_{d\mid n}\mu(d)\) for every \(n\), what is \(g(12)\)?
  5. What is \(\mu(4)\)?
  6. If \(g(n)=n\) for all \(n\), compute \(f(6)\) using Möbius inversion.
  7. If \(g(n)=n^2\) for all \(n\), compute \(f(3)\) using Möbius inversion.
  8. If \(g(n)=\sum_{d\mid n}f(d)\) and \(f(n)=n\) for all \(n\), compute \(g(4)\).
  9. Let \(g(n)=n\) for all \(n\). What is \(f(12)\) by Möbius inversion?
  10. A student claims that \(f(n)=\sum_{d\mid n}g(d)\) inverts \(g(n)=\sum_{d\mid n}f(d)\). With \(g(n)=n\), what happens for \(n=6\)?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 6
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 4