Proof to a property of Euler's totient function

Question

The property is $$\sum_{d|n}\phi(d) = n$$

And the proof provided is

If $d$ divides $n$, let $C_d$ be the unique subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d$, and let $\Phi_d$ be the set of generators of $C_d$. Since all elements of $\mathbb{Z}/n\mathbb{Z}$ generate one of the $C_d$, the group $\mathbb{Z}/n\mathbb{Z}$ is the disjoint union of the $\Phi_d$ and we have
$$n = \text{Card}(\mathbb{Z}/n\mathbb{Z}) = \sum_{d|n}\text{Card}(\Phi_d) = \sum_{d|n}\phi(d)$$

But I can't prove to myself the uniqueness of the subgroups to let the rest fall together.

Answer 1

As I understand your question, you need to prove in $\Bbb Z/n\Bbb Z$, there is a unique subgroup of order $d$ where $d|n$. Suppose, $m\in\Bbb Z/n\Bbb Z$, then $|m|$,the order of $m$, is $n/(n,m)$. So, if a subgroup $H$ has order $d$, then it is generated by $m$ where $n/(n,m)=d$. Clearly $m=n/d$ is such a number. Any other such number must be a multiple of $n/d$, hence all possible generators of a group of order $d$ belong to the same subgroup.

Answer 2

You can prove it using induction on number prime divisor.

Suppose $\displaystyle k=p^r$ be a integer which has one prime divisor $p$

Then divisors of $k$ are $1, p,.......p^r$. So $$\displaystyle\sum_{d|p^r}\phi(d)=\phi(1)+\phi(p)+.....\phi(p^r)=1+p-1+....p^r-p^{r-1}=p^r$$

Now suppose this is true for all those integers which have $s$ prime factors.

consider $Z=mq^t$ where m is an integer which have $s$ prime factor and q is a prime and $gcd(m,q)=1$

Then$$\displaystyle\sum_{d|\phi(Z)}\phi(Z)=\sum_{d|m}\Big(\phi(m)+\phi(mq)+\phi(mq^2)+......\phi(mq^t)\Big)=\sum_{d|m}\Big(\phi(m)+\phi(m)\phi(q)+\phi(m)\phi(q^2)+.....\phi(m)\phi(q^2)\Big)=\Big(\sum_{d|m}\phi(m)\Big)\Big(\phi(1)+\phi(q)+.....\phi(q^t)\Big)=mq^t=Z$$

And therefore $$Z=\sum_{d|\phi(Z)}\phi(Z)$$. So it completes the proof of result.