Difference between revisions of "Mobius function"
| Line 2: | Line 2: | ||
<cmath>\mu(n) = \begin{cases} 0 & d^2 | n, \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}</cmath> | <cmath>\mu(n) = \begin{cases} 0 & d^2 | n, \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}</cmath> | ||
In addition, <math>\mu(1) = 1</math>. | In addition, <math>\mu(1) = 1</math>. | ||
| + | |||
| + | 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 <math>n</math> and relatively prime to <math>n</math>, 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 | ||
| + | <cmath>\phi(n) = \sum_{d|n} d \mu\left(\frac{n}{d}\right).</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}\]](http://latex.artofproblemsolving.com/7/f/5/7f54ff985c575ba980c7a2a4e45a26dd2af7481f.png)
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
![\[\phi(n) = \sum_{d|n} d \mu\left(\frac{n}{d}\right).\]](http://latex.artofproblemsolving.com/7/4/5/745b1c3b13454ca1dfc6b7a9728ac1c689fc2095.png)
