Difference between revisions of "Mobius function"
| Line 7: | Line 7: | ||
First, it conveniently encodes [[Principle of Inclusion-Exclusion]]. | 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 | 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 | ||
| − | + | {| class="wikitable" style="margin: 1em auto 1em auto" | |
| − | \phi(n) = | + | | <math>\phi(n)</math> || <math> =n</math> |
| − | + | |- | |
| − | + | | || <math>- \frac{n}{p_1} - \frac{n}{p_2} - \cdots - \frac{n}{p_k}</math> | |
| − | + | |- | |
| − | + | | || <math>+ \frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots + \frac{n}{p_{k-1}p_k}</math> | |
| − | + | |- | |
| + | | || <math>\vdots</math> | ||
| + | |- | ||
| + | | || <math>+ (-1)^k \frac{n}{p_1 p_2 \cdots p_k},</math> | ||
| + | |} | ||
| + | |||
more succinctly expressed as | more succinctly expressed as | ||
<cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath> | <cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath> | ||
| + | |||
| + | One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that | ||
| + | <cmath>\sum_{d|n} mu(d) = \begin{cases} 1 & n = 1, \\ (0 & otherwise. \end{cases}</cmath> | ||
Revision as of 19:41, 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
 |
|
| |
| |
| |
|
more succinctly expressed as
![\[\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.\]](http://latex.artofproblemsolving.com/c/6/3/c63119d59e6350c74a8f0874d361bd48137f8620.png)
One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that
![\[\sum_{d|n} mu(d) = \begin{cases} 1 & n = 1, \\ (0 & otherwise. \end{cases}\]](http://latex.artofproblemsolving.com/c/7/7/c7761b997bccb25b9d6ce60a3fd8b6833b220396.png)
