Prove that $\sum_{k \mid n} \varphi(k) = n$, where $\varphi(n)$ is Euler's totient function.
Proposed as exercise 3.49 in Abstract Algebra: An Introductory Course, by Gregory T. Lee.
By means of the fundamental theorem of arithmetic let first $n=p_1^{\alpha_1}
p_2^{\alpha_2}\cdots p_m^{\alpha_m}$; the proof will proceed by induction on
$m$.
For the base case, when $n=p^\alpha$ it follows that $$ \begin{alignat*}5 p^\alpha &= (p^\alpha - p^{\alpha-1}) &&+ (p^{\alpha-1} - p^{\alpha-2}) &&+ \cdots &&+ (p - 1) &&+ 1\\ &= \varphi(p^\alpha) &&+ \varphi(p^{\alpha-1}) &&+ \cdots &&+ \varphi(p) &&+ \varphi(1) = \sum_{k \mid p^\alpha} \varphi(k). \end{alignat*} $$
Thus, having $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} p_{m+1}^{\alpha_{m+1}}$ observe that $$ \begin{align*} \sum_{k \mid n} \varphi(k) &= \sum_{i = 0}^{\alpha_{m+1}} \sum_{\substack{k\mid n\\p_{m+1}\nmid k}} \varphi(k\cdot p_{m+1}^i) = \sum_{i = 0}^{\alpha_{m+1}} \varphi(p_{m+1}^i) \sum_{\substack{k\mid n\\p_{m+1}\nmid k}} \varphi(k)\\ &\stackrel{\text{IH}}{=} p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} \sum_{i = 0}^{\alpha_{m+1}} \varphi(p_{m+1}^i) \stackrel{\text{IH}}{=} p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} p_{m+1}^{\alpha_{m+1}} = n, \end{align*} $$ as it was to be shown.
For the base case, when $n=p^\alpha$ it follows that $$ \begin{alignat*}5 p^\alpha &= (p^\alpha - p^{\alpha-1}) &&+ (p^{\alpha-1} - p^{\alpha-2}) &&+ \cdots &&+ (p - 1) &&+ 1\\ &= \varphi(p^\alpha) &&+ \varphi(p^{\alpha-1}) &&+ \cdots &&+ \varphi(p) &&+ \varphi(1) = \sum_{k \mid p^\alpha} \varphi(k). \end{alignat*} $$
Thus, having $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} p_{m+1}^{\alpha_{m+1}}$ observe that $$ \begin{align*} \sum_{k \mid n} \varphi(k) &= \sum_{i = 0}^{\alpha_{m+1}} \sum_{\substack{k\mid n\\p_{m+1}\nmid k}} \varphi(k\cdot p_{m+1}^i) = \sum_{i = 0}^{\alpha_{m+1}} \varphi(p_{m+1}^i) \sum_{\substack{k\mid n\\p_{m+1}\nmid k}} \varphi(k)\\ &\stackrel{\text{IH}}{=} p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} \sum_{i = 0}^{\alpha_{m+1}} \varphi(p_{m+1}^i) \stackrel{\text{IH}}{=} p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m} p_{m+1}^{\alpha_{m+1}} = n, \end{align*} $$ as it was to be shown.
Here, the following two well-known facts were used without proof:
- $\varphi(p^k) = p^k - p^{k-1}$.
- $\varphi(mn) = \varphi(m)\varphi(n)$ when $m$ and $n$ are coprime.