Sum of Möbius Function over Divisors

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Möbius_Function_over_Divisors&oldid=676319"