Mobius function

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

$\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_1 p_2 \cdots p_k},$

more succinctly expressed as $\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.$

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}$

Page

Toolbox

Search

Mobius function