Exercise :
Using the fact that the number of the generators of $\mathbb Z_d$ is $\phi(d)$, show that :
$$n = \sum_{d|n} \phi(d)$$
where $\phi$ is Euler's function which is defined for every positive integer $n$ from the formula $\phi(n)=s$, where $s$ is the number of positive integers less or equal of $n$ which are prime to $n$.
QUESTION : I have proved the given relation the following way, whilst studying but I am not sure whether it could be smaller or alternated, using the fact given in the exercise about $\mathbb Z_d$. I would appreciate any clarification or hint given.
Let $S_d = \left\{{m \in \mathbb Z: 1 \le m \le n, \gcd \left\{{m, n}\right\} = d}\right\}$. That is, $S_d$ is all the numbers less than or equal to $n$ whose $\text{gcd}$ with $n$ is $d$.
Now from Divide by $\text{gcd}$ for Coprime Integers we have:
$$\gcd \left\{{m, n}\right\} = d \iff \dfrac m d, \dfrac n d \in \mathbb Z: \dfrac m d \perp \dfrac n d$$
So the number of integers in $S_d$ equals the number of positive integers no bigger than $n/d$ which are prime to $n/d$.
By definition of the Euler function stated in the exercise, this is :
$$|S_d| = \phi\bigg(\frac{n}{d}\bigg)$$
From the definition of the $S_d$, it follows that for all $1≤m≤n$ :
$$\exists d | n: m \in S_d$$
which leads to :
$$\displaystyle \left\{{1, \ldots, n}\right\} = \bigcup_{d |n} S_d$$
From the way I defined $S_d$ though, it also follows that they are pairwise disjoint.
Now from Corollary to Cardinality of Set Union, it follows that :
$$n=\sum_{d|n} |S_d| = \sum_{d|n} \phi \left({\dfrac n d}\right)$$
But using the fact that the sum over divisors equals the sum over quotients, we derive the formula wanted :
$$\sum_{d | n} \phi \left({\dfrac n d}\right) = \sum_{d |n} \phi \left({d}\right)$$
Best Answer
The idea is you want to count the elements in $\mathbb{Z}_{n}$ in two ways. First, we note that $|\mathbb{Z}_{n}| = n$. We now count in a second way. Recall that for every $1\leq d|n$, there exists a unique subgroup of order $d$ in $\mathbb{Z}_{n}$, which is precisely $\mathbb{Z}_{d}$. Furthermore, these are the only subgroups of $\mathbb{Z}_{n}$. Now count the generators of $\mathbb{Z}_{d}$; there are $\phi(d)$ such generators. By Lagrange's Theorem, we have that $\langle a \rangle$ is a subgroup of $\mathbb{Z}_{n}$ for every $a \in \mathbb{Z}_{n}$. So in fact:
$$\sum_{1 \leq d|n} \phi(d) = n$$