Difference between revisions of "Mobius function"
| Line 30: | Line 30: | ||
Property 2:If <math>F(n)=\sum_{d|n} f(d)</math> for every positive integer <math>n</math>, then <cmath>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})</cmath>. | Property 2:If <math>F(n)=\sum_{d|n} f(d)</math> for every positive integer <math>n</math>, then <cmath>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})</cmath>. | ||
| − | Proof:We have <cmath>\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|n/d}f(k)=\sum_{k|n}\sum_{d|n/k}\mu(d)f(k) | + | Proof:We have <cmath>\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|n/d}f(k)=\sum_{k|n}\sum_{d|n/k}\mu(d)f(k) =\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)</cmath> . |
| − | |||
| − | =\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)</cmath> . | ||
The Mobius function is also closely related to the [[Riemann zeta function]], as | The Mobius function is also closely related to the [[Riemann zeta function]], as | ||
<cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath> | <cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath> | ||
Revision as of 23:05, 21 September 2020
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 & \text{otherwise}. \end{cases}\]](http://latex.artofproblemsolving.com/4/9/0/49042853bc6d6ca51d53632b6e73a0e41d165958.png)
Property 1: The function 
is multiplicative .
Proof:If 
or 
for a prime 
, we are done.Else let 
and 
where 
,then 
.
Property 2:If 
for every positive integer , then ![\[f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\]](http://latex.artofproblemsolving.com/2/a/a/2aafc11052e98e8ed170fad55102e802de634b6e.png)
.
Proof:We have ![\[\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|n/d}f(k)=\sum_{k|n}\sum_{d|n/k}\mu(d)f(k) =\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)\]](http://latex.artofproblemsolving.com/8/1/f/81f7989ef8419d474e6084c7befc2eaca8df716a.png)
.
The Mobius function is also closely related to the Riemann zeta function, as
![\[\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.\]](http://latex.artofproblemsolving.com/d/d/c/ddc6c9692c6e84188d84b05712cdf106fc5d4e89.png)
