(i) Prove that
$$ \sum _{d \mid p^k} \phi (d) = p^k $$
where $p$ is prime.
(ii) Prove that
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') = p^kq^m $$
where $p$ and $q$ are distinct primes.
(iii) Prove Gauss’s Theorem, that is, for any natural number $n$ we have
$$ \sum _{d \mid n} \phi (d) = n $$
This (iii) is an astonishing result proved by Gauss.
(i) Since $p$ is prime, the only divisors of $p^k$ are
$$ 1, \; p, \; p^2, \; p^3, \; \ldots, \; p^{k-1}, \; p^k $$
And the Euler totient function values of these divisors are
$$ 1, \; (p-1), \; p(p - 1), \; p^2(p-1), \; \ldots , \; p^{k-2}(p-1) , \; p^{k-1}(p-1) $$
The sum of these is
$$ \sum _{d \mid p^k} \phi (d) = 1 + (p-1) + (p^2 -p) + (p^3 -p^2) + \ldots + (p^{k-1}-p^{k-2}) + (p^k - p^{k-1}) $$
The sum reduces because the second term in each bracket is cancelled by the first term of the previous bracket. And so
$$ \sum _{d \mid p^k} \phi (d) = p^k $$
(ii) Since $p$ is prime, the only divisors of $p^k$ are
$$ 1, \; p, \; p^2, \; p^3, \; \ldots, \; p^{k-1}, \; p^k $$
Similarly, since $q$ is a prime, the only divisors of $q^m$ are
$$ 1, \; q, \; q^2, \; q^3, \; \ldots, \; q^{m-1}, \; q^m $$
Since $p$ and $q$ are distinct primes, the factors of $p^kq^m$ are the products of every possible choice of elements from each list above.
$$ \begin{align} & 1(1), \; p(1), \; p^2(1), \; p^3(1), \; \ldots, \; p^{k-1}(1), \; p^k(1), \\ \\ & 1(q), \; p(q), \; p^2(q), \; p^3(q), \; \ldots, \; p^{k-1}(q), \; p^k(q), \\ \\ & 1(q^2), \; p(q^2), \; p^2(q^2), \; p^3(q^2), \; \ldots, \; p^{k-1}(q^2), \; p^k(q^2), \\ \\ & \vdots \\ \\ & 1(q^m), \; p(q^m), \; p^2(q^m), \; p^3(q^m), \; \ldots, \; p^{k-1}(q^m), \; p^k(q^m) \end{align} $$
That is
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') $$
Using the result from part (i), we have $ \sum _{d \mid p^k} \phi(d) = p^k$ and $\sum _{d' \mid q^m} \phi (d') = q^m$, and so
$$ \sum _{d \mid p^kq^m} \phi (d) = \sum _{d \mid p^k} \phi (d) \sum _{d' \mid q^m} \phi (d') = p^kq^m $$
(iii) We will use induction.
Let $P(z)$ be the following statement referring to a natural number $n_z=p_1^{k_1}p_2^{k_2}\ldots p_z^{k_z}$ which has $z$ distinct primes in its prime decomposition.
$$ P(z) \quad := \quad \sum _{d \mid n_z} \phi (d) = n_z $$
We need to prove the base case $P(1)$ and the inductive step $P(z) \implies P(z+1)$.
Base Case $P(1)$
The base case $P(1)$ is, for some prime $p$ and natural number $k$
$$ P(1) \quad := \quad \sum _{d \mid n_1} \phi (d) = n_1 = p^k $$
This was proved in part (i) above, and so the base case is true. Indeed, in part (ii) we proved $P(2)$.
Inductive Step $P(z) \implies P(z+1)$
We assume $P(z)$ is true, the induction hypothesis, and aim to show $P(z+1)$
$$ P(z+1) \quad := \quad \sum _{d \mid n_{z+1}} \phi (d) = n_{z+1} $$
We first note that any divisor $d_{z+1}$ of $n_{z+1}$ is a product of a divisor $d_z$ of $n_z$ and a divisor $d'$ of $p_{z+1}^{k_{z+1}}$.
$$ d_{z+1} = d_z \times d' $$
Since $d_z$ and $d'$ are coprime, we have
$$ \phi(d_{z+1}) = \phi(d_z) \times \phi(d') $$
And so the sum of the Euler totient function of the divisors of $n_{z+1}$ is
$$ \begin{align} \sum_{d_{z+1}} \phi(d_{z+1}) & = \sum_{d_z, \; d'} \left ( \phi(d_z) \times \phi(d') \right ) \\ \\ &= \sum_{d_z \mid n_z} \phi(d_z) \times \sum_{d' \mid p_{z+1}^{k_{z+1}}} \phi(d') \end{align}$$
The induction hypothesis $P(z)$ gives us
$$ \sum_{d_{z+1}\mid n_{z+1}} \phi(d_{z+1}) = n_z \times \sum_{d' \mid p_{z+1}^{k_{z+1}}} \phi(d') $$
And the result from part (i) gives us
$$ \begin {align} \sum_{d_{z+1}\mid n_{z+1}} \phi(d_{z+1}) & = n_z \times p_{z+1}^{k_{z+1}} \\ \\ & = n_{z+1} \end{align} $$
And so $P(z+1)$ is true if $P(z)$ is true.
By induction we have proved Gauss’s Theorem, that is, for any natural number $n$ we have
$$ \sum _{d \mid n} \phi (d) = n $$