Derivation of Euler's Totient Sum Formula
Formula
If the divisors of $n$ are $d_{1}, d_{2} , \cdots , d_{r}$, then $$ n = \sum_{ i = 1 }^{r} \phi (d_{i}) = \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r}) $$
Explanation
The totient function may feel like a somewhat unnatural concept from the very moment it is defined. But given the totient theorem as well as formulas like this one, one cannot help but admit that it is a function genuinely needed somewhere within the truths of mathematics.
For example, consider $15$: it has the divisors $1,3,5,15$. Carrying out the actual computation gives the following. $$ \begin{align*} \phi (1) + \phi (3) + \phi (5) + \phi (15) =& \phi (1) + \phi (3) + \phi (5) + \phi (3) \phi (5) \\ =& 1 + 2 + 4 + 2 \cdot 4 \\ =& 15 \end{align*} $$
Derivation
Define $F(n) := \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r})$; it suffices to show that $F(n) = n$.
Case 1. $n$ is a prime
If we let $n = p^{k}$ be a power of the prime $p$, then $$ \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k}) \\ =& 1 + (p-1) + \cdots + (p^{k} - p^{k-1}) \\ =& p^{k} \end{align*} $$
Case 2. $n$ is a product of powers of two primes $p,q$
If we let $n = p^{k_{p}} q^{k_{q}}$, then $$ \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots + \phi (p^{k_{p}}) + \phi (q) + \cdots + \phi (q^{k_{q}}) \\ & + \phi (pq) + \phi (p^{2}q) + \phi (pq^{2}) + \cdots + \phi (p^{k_{p}} q^{k_{q}}) \end{align*} $$ By the multiplicative property of the totient function, $$ \begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) + \phi (q) + \cdots \phi (q^{k_{q}}) \\ & + \phi (p) \phi (q) + \phi (p^{2}) \phi (q) + \phi (p) \phi (q^{2}) + \cdots \phi (p^{k_{p}}) \phi ( q^{k_{q}}) \\ =& \left[ \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) \right] \left[ 1 + \phi (q) + \cdots \phi (q^{k_{q}}) \right] \\ =& F(p^{k_{p}}) F(q^{k_{q}}) \end{align*} $$
Case 3. $n$ is an arbitrary natural number
By the fundamental theorem of arithmetic, $n$ can be expressed as $n = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}}$. $$ \begin{align*} F(n) =& F(p_{1}^{k_{1}}) F(p_{2}^{k_{2}}) \cdots F(p_{s}^{k_{s}}) \\ =& p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}} \\ =& n \end{align*} $$ Therefore, in every case $F(n) = n$ holds.
■