Difference between revisions of "Mobius function"

Line 15: Line 15:
 
\end{align*}
 
\end{align*}
 
more succinctly expressed as
 
more succinctly expressed as
<cmath>\phi(n) = \sum_{d|n} d \mu\left(\frac{n}{d}\right).</cmath>
+
<cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath>

Revision as of 19:32, 26 January 2011

The Mobius function is a multiplicative number theoretic function defined as follows: \[\mu(n) = \begin{cases} 0 & d^2 | n, \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}\] In addition, $\mu(1) = 1$.

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 $n$ and relatively prime to $n$, 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 \[\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.\]