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 \divides n}$ denote the sum over all of the divisors of $n$.

Let $\map \mu d$ be the Möbius function.


$\displaystyle \sum_{d \mathop \divides n} \map \mu d = \floor {\frac 1 n}$

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 \divides n} \map \mu d$ the only non-zero terms come from $d = 1$ and the divisors of $n$ which are products of distinct primes.


\(\displaystyle \sum_{d \mathop \divides n} \map \mu d\) \(=\) \(\displaystyle \map \mu 1 + \map \mu {p_1} + \dotsb + \map \mu {p_k} + \map \mu {p_1 p_2} + \dotsb + \map \mu {p_{k - 1} p_k} + \dotsb + \map \mu {p_1 p_2 \dotsm p_k}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom k 0 + \dbinom k 1 \paren {-1} + \dbinom k 2 \paren {-1}^2 + \cdots + \dbinom k k \paren {-1}^k\)
\(\displaystyle \) \(=\) \(\displaystyle 0\) Alternating Sum and Difference of Binomial Coefficients for Given n

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