Mobius function
The Mobius function is a multiplicative number theoretic function defined as follows:
In addition,
.
The Mobius function is useful for a variety of reasons.
First, it conveniently encodes Principle of Inclusion-Exclusion.
For example, to count the number of positive integers less than or equal to and relatively prime to
, we have
\begin{align*}
\phi(n) = &n
&- \frac{n}{p_1} - \frac{n}{p_2} - \cdots - \frac{n}{p_k} &+ \frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots + \frac{n}{p_{k-1}p_k} &\vdots &+ (-1)^k \frac{n}{p_1p_2\cdots p_k},
\end{align*}
more succinctly expressed as