User:Caliburn/s/4
Theorem
Let $n \ge 2$ be an integer.
Let $k$ be the number of distinct prime divisors of $n$.
Then:
- $\ds \sum_{d \divides n} \size {\map \mu d} = 2^k$
where $\mu$ denotes the Moebius function.
Proof
By the Fundamental Theorem of Arithmetic, we can factorise:
- $\ds n = \prod_{i \mathop = 1}^k p_i^{\alpha_i}$
for primes $p_i$ and non-negative integers $\alpha_i$, with $p_i \ne p_j$ for $i \ne j$.
Then any divisor $d$ of $n$ will have the form:
- $\ds d = \prod_{i \mathop = 1}^k p_i^{\beta_i}$
where $0 \le \beta_i \le \alpha_i$.
Note that if $\beta_i \ge 2$ for any $i$, $d$ is not square-free, so we would have:
- $\map \mu d = 0$
in this case, by the definition of the Moebius function.
So:
- $\map \mu d \ne 0$
only if $d$ is the product of distinct primes, or $d = 1$.
Note that:
- $\ds \sum_{d \divides n} \size {\map \mu d} = \map \mu 1 + \sum_{d \divides n, \, d \ne 1} \size {\map \mu d} = 1 + \sum_{d \divides n, \, d \ne 1} \size {\map \mu d}$
We can decompose the latter sum:
- $\ds \sum_{d \divides n, \, d \ne 1} \size {\map \mu d} = \sum_{i \mathop = 1}^k \paren {\sum_{d \divides n, \, d \text { product of primes}, \, \map \omega d = i} \size {\map \mu d} }$
Note that from the definition of the Moebius function, we have:
- $\size {\map \mu d} = 1$
since $d$ is square-free.
So, we wish to compute:
- $\ds \sum_{d \divides n, \, d \text { product of primes}, \, \map \omega d = i} 1$
for each $i$.
That is, we wish to count how many products of $i$ primes divide $n$.
From Euclid's Lemma, each of these primes must divide $n$.
That is, we simply aim to count how many ways we can pick $i$ primes from the set of $k$ primes $\set {p_k}$.
So, from the definition of the Definition:Binomial Coefficient:
- $\ds \sum_{d \divides n, \, d \text { product of primes}, \, \map \omega d = i} 1 = \binom k i$
Then:
\(\ds \sum_{d \divides n} \size {\map \mu d}\) | \(=\) | \(\ds 1 + \sum_{i \mathop = 1}^k \binom k i\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^k \binom k i\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2^k\) | Binomial Theorem |