Sum of Möbius Function over Divisors
Theorem
Let $n \in \Z_{>0}$, i.e. let $n$ be a strictly positive integer.
Let $\ds \sum_{d \mathop \divides n}$ denote the sum over all of the divisors of $n$.
Let $\map \mu d$ be the Möbius function.
Then:
- $\ds \sum_{d \mathop \divides n} \map \mu d = \floor {\frac 1 n}$
where $\floor {\dfrac 1 n}$ is the floor of $\dfrac 1 n$.
Proof
The theorem 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 $\ds \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.
From the definition of the Möbius function, the Möbius function of a product of $m$ distinct primes is $\paren {-1}^m$.
From the definition of Binomial coefficient, there are $\dbinom k m$ ways to choose $m$ primes from $p_1, p_2, \dots, p_k$ to multiply together.
So among the divisors of $p_1 p_2 \dotsm p_k$, there are exactly $\dbinom k m$ numbers that are the product of $m$ distinct primes.
Thus:
\(\ds \sum_{d \mathop \divides n} \map \mu d\) | \(=\) | \(\ds \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}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dbinom k 0 + \dbinom k 1 \paren {-1} + \dbinom k 2 \paren {-1}^2 + \cdots + \dbinom k k \paren {-1}^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 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}$.
$\blacksquare$
Examples
$n = 210$
- $\ds \sum_{d \mathop \divides 210} \map \mu d = 0$
Sources
- 1976: Tom M. Apostol: Introduction to Analytic Number Theory ... (previous) ... (next): $2.2$: The Möbius function $\map \mu n$