Summing the Euler $\varphi$-function $\varphi(n)$

Question

The Euler $\varphi$-function $\varphi(n)$ counts the number of positive integers less than or equal to $n$, which are relatively prime with $n$. I would like to evaluate

$$ \sum_{d\mid n}\varphi(d) $$and prove that the answer is correct.

Answer 1

Define the sets $A_q = \{(n,k)=q \mid 1 \leq k \leq n\}$. As you can see, total number of elements of $A_1, \dots, A_n$ is equal to $n$ since for each $i \neq j $, $A_i \cap A_j = \emptyset $.

Now let us check how many elements does $A_d$ have: If $x \in A_d$ then $(n,x)=d$ so that $(\frac{n}{d},\frac{x}{d})=1$. Then we can say that the number of such $x$'s is equal to $\varphi(\frac{n}{d})$. $\implies |A_d|=\varphi(\frac{n}{d})$.

Going back to our sum:

$\sum_{d \mid n} \varphi(d) = \sum_{d\mid n}\varphi(\frac{n}{d})= \sum_{d \mid n}|A_d| =n$ as desired.

Answer 2

$\varphi(n)$ is a multiplicative function, i.e. $$\varphi(a b) = \varphi(a)\cdot\varphi(b) \tag{0}$$ for any $a,b\in\mathbb{N}^+$ such that $\gcd(a,b)=1$. By assuming that $$ n = p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k} $$ is the factorization of $n$, from $(0)$ we have: $$ \sum_{d\mid n}\varphi(d) = \prod_{j=1}^{k}\sum_{h=0}^{\alpha_j}\varphi(p_j^h) \tag{1}$$ but: $$ \varphi(p^h) = p^{h}-p^{h-1}, \tag{2}$$ hence the RHS of $(1)$ contains a telescopic sum and: $$ \sum_{d\mid n}\varphi(d) = \prod_{j=1}^{k} p_j^{\alpha_j}=\color{red}{n}.\tag{3}$$

Another (group-theoretic) proof is just on the Wikipedia page about the totient function.