Summing the Euler $\varphi$-function $\varphi(n)$ 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.
 A: $\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.
A: 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.
