Sum of Moebius Function over Divisors

Theorem

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

Then

$\displaystyle \sum_{d \backslash n} \mu \left({d}\right) \frac n d = \phi \left({n}\right)$

where:

• $\displaystyle \sum_{d \backslash n}$ denotes the sum over all of the divisors of $n$
• $\phi \left({n}\right)$ is the Euler $\phi$ function, the number of integers less than $n$ that are prime to $n$
• $\mu \left({d}\right)$ is the Moebius function.

Equivalently, this says that

$\phi = \mu * I_{\Z_{>0}}$

where:

$*$ denotes Dirichlet convolution

$I_{\Z_{>0}}$ denotes the identity mapping on $\Z_{>0}$, that is: $\forall n \in \Z, n \ge 1: I_{\Z_{>0}}: n \mapsto n$.

Proof

Lemma

$\displaystyle \sum_{d \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.

Proof of Lemma

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 \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 \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \sum_{d \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 \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle {k \choose 0} + {k \choose 1} (-1) + {k \choose 2} (-1)^2 + \cdots + {k \choose k}(-1)^k\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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

$\blacksquare$

Proof of Theorem

If $1(k) = 1$ is the unity function, then $\phi$ is defined as:

$\displaystyle \phi(n) = \sum_{k \perp n} 1(k)$

Since $\gcd(n,k)$ is $1$ if $k \perp n$ and $0$ otherwise, we can rewrite the above sum as:

$\displaystyle \sum_{k=1}^n \left \lfloor {\frac{1}{\gcd(n,k)}} \right \rfloor$

Now we may use the lemma, with $\gcd(n,k) \ $ replacing $n$, to get:

$\displaystyle \phi(n) = \sum_{k=1}^n \left({\sum_{d \backslash \gcd(n,k)} \mu(d)}\right) = \sum_{k=1}^n \sum_{ { {d \backslash n} \choose {d \backslash k}}} \mu(d)$

For a fixed divisor $d$ of $n$, we must sum over all those $k$ in the range $1 \leq k \leq n$ which are multiples of $d$.

If we write $k = q d$, then $1 \leq k \leq n$ if and only if $1 \leq q \leq \dfrac n d$.

Hence the last sum for $\phi(n)$ can be written as:

$\displaystyle \phi(n) = \sum_{d \backslash n} \left({\sum_{q=1}^{\tfrac n d} \mu(d) }\right) = \sum_{d \backslash n} \mu(d) \sum_{q=1}^{\tfrac n d} 1(q) = \sum_{d \backslash n} \mu(d)\dfrac n d$

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 25 \beta$