Möbius Inversion Formula
The Möbius Inversion Formula is a mathematical tool used in number theory to relate two arithmetic functions. It allows one to express a function defined as a sum over divisors in terms of another function, effectively reversing the summation process. This is particularly useful for solving problems involving divisor sums.
In its simplest form, if f(n) is a function defined by a sum over its divisors, the Möbius function \mu(d) can be used to invert this relationship. The formula states that g(n) = \sum_d|n f(d) can be inverted to find f(n) using f(n) = \sum_d|n \mu(d) g(n/d) .