Sum of Möbius Function over Divisors/Lemma

From ProofWiki
Jump to navigation Jump to search

Lemma to Sum of Möbius Function over Divisors

Let $n \in \Z_{>0}$, i.e. let $n$ be a strictly positive integer.

Let $\displaystyle \sum_{d \mathop \backslash n}$ denote the sum over all of the divisors of $n$.

Let $\mu \left({d}\right)$ be the Möbius function.


$\displaystyle \sum_{d \mathop \backslash n} \mu \left({d}\right) = \left \lfloor {\frac 1 n} \right \rfloor$

That is:

$\mu * u = \iota$

where $u$ and $\iota$ are the unit arithmetic function and identity arithmetic function respectively.


The lemma is clearly true if $n=1$.

Assume, then, that $n > 1$ and write, by the Fundamental Theorem of Arithmetic:

$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$

In the sum $\displaystyle \sum_{d \mathop \backslash n} \mu \left({d}\right)$ the only non-zero terms come from $d=1$ and the divisors of n which are products of distinct primes.

Thus from Alternating Sum and Difference of Binomial Coefficients for Given n:

\(\displaystyle \) \(\) \(\displaystyle \sum_{d \mathop \backslash n} \mu \left({d}\right) = \mu(1) + \mu(p_1) + \cdots + \mu(p_k) + \mu(p_1p_2) + \dots + \mu(p_{k-1}p_k) + \dots + \mu(p_1p_2\dots p_k)\)
\(\displaystyle \) \(=\) \(\displaystyle {k \choose 0} + {k \choose 1} (-1) + {k \choose 2} (-1)^2 + \cdots + {k \choose k}(-1)^k\)
\(\displaystyle \) \(=\) \(\displaystyle 0\)

Hence, the sum is $1$ for $n=1$, and $0$ for $n>1$, which are precisely the values of $\left \lfloor {\dfrac 1 n} \right \rfloor$.