TAOCP 4.5.3 Exercise 28
Let $1(n)$ denote the constant function $1$, and let $\delta_{n1}$ be $1$ when $n=1$ and $0$ otherwise.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 28. [M23] Prove the following identities involving the three number-theoretic functions $\varphi(n)$, $\mu(n)$, $\Lambda(n)$:
$$\text{a)};\sum_{d|n} \mu(d) = \delta_{n1}, \qquad \text{b)};\ln n = \sum_{d|n} \Lambda(d), \qquad n = \sum_{d|n} \varphi(d).$$
$$\text{c)};\Lambda(n) = \sum_{d|n} \mu!\left(\frac{n}{d}\right)\ln d, \qquad \varphi(n) = \sum_{d|n} \mu!\left(\frac{n}{d}\right) d.$$
Verified: yes
Solve time: 1m29s
Solution
Let $1(n)$ denote the constant function $1$, and let $\delta_{n1}$ be $1$ when $n=1$ and $0$ otherwise.
a)
By definition, $\mu(n)$ is the Möbius function. A fundamental property of Möbius inversion is that $\mu$ is the Dirichlet inverse of $1$; equivalently,
$$ \sum_{d\mid n}\mu(d)=\delta_{n1}. $$
A direct verification is possible from the prime factorization of $n$.
If $n=1$, the sum consists only of the term $\mu(1)=1$.
If
$$ n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}, \qquad r\ge1, $$
then only squarefree divisors contribute. Hence
$$ \sum_{d\mid n}\mu(d) =\sum_{S\subseteq{1,\ldots,r}}(-1)^{|S|} =(1-1)^r =0. $$
Therefore
$$ \boxed{\sum_{d\mid n}\mu(d)=\delta_{n1}}. $$
b)
For every integer $n\ge1$,
$$ \sum_{d\mid n}\Lambda(d) $$
receives contributions only from divisors of the form $p^k$, where $p$ is prime. If
$$ n=\prod_{i=1}^r p_i^{\alpha_i}, $$
then
$$ \sum_{d\mid n}\Lambda(d) =\sum_{i=1}^r\sum_{k=1}^{\alpha_i}\Lambda(p_i^k) =\sum_{i=1}^r\sum_{k=1}^{\alpha_i}\ln p_i =\sum_{i=1}^r\alpha_i\ln p_i =\ln n. $$
Thus
$$ \boxed{\ln n=\sum_{d\mid n}\Lambda(d)}. $$
For Euler's totient function, let
$$ F(n)=\sum_{d\mid n}\varphi(d). $$
Using the well-known interpretation of $\varphi(d)$ as the number of integers $m$ with $1\le m\le d$ and $\gcd(m,d)=1$, every integer $k$ with $1\le k\le n$ can be written uniquely as
$$ k=g m,\qquad n=g d, $$
with $\gcd(m,d)=1$. Therefore the integers $1,\ldots,n$ are partitioned according to the divisor $d$ of $n$, and there are exactly $\varphi(d)$ integers in the class corresponding to $d$. Hence
$$ n=\sum_{d\mid n}\varphi(d). $$
Therefore
$$ \boxed{n=\sum_{d\mid n}\varphi(d)}. $$
c)
Part (b) gives
$$ \ln n=\sum_{d\mid n}\Lambda(d). $$
Applying Möbius inversion, using part (a),
$$ \Lambda(n) =\sum_{d\mid n}\mu!\left(\frac nd\right)\ln d. $$
Similarly, from
$$ n=\sum_{d\mid n}\varphi(d), $$
another application of Möbius inversion yields
$$ \varphi(n) =\sum_{d\mid n}\mu!\left(\frac nd\right)d. $$
Hence
$$ \boxed{\Lambda(n)=\sum_{d\mid n}\mu!\left(\frac nd\right)\ln d}, \qquad \boxed{\varphi(n)=\sum_{d\mid n}\mu!\left(\frac nd\right)d}. $$
This completes the proof.
∎