# $n$ positive integer, then $n=\sum_{d|n} \phi(d)$ (proof Rotman's textbook)

I've just read in Rotman's group theory textbook the proof of the following statement:

Statement

If $n$ is a positive integer, then $$n=\sum_{d|n} \phi(d),$$

where the sum is over all divisors $d$ of $n$ with $1 \leq d \leq n$.

Proof. If $C$ is a cyclic subgroup of a group $G$, let $gen(C)$ denote the set of all its generators. It is clear that $G$ is the disjoint union $G = \coprod gen(C)$, where $C$ ranges over all the cyclic subgroups of $G$. We have just seen, when $G$ is cyclic of order $n$, that there is a unique cyclic subgroup $C_d$ of order $d$ for every divisor $d$ of $n$. Therefore, $n = |G| = \sum_{d|n}|gen(C_d)|$. In Exercise 2.20, however, we saw that $|gen(C_d)| = \phi(d)$; the result follows.

This is a very nice result and the proof is pretty short and simple, however I have a basic doubt, I don't see why $$G= \coprod gen(C)$$

it is evident that any generator is an element of $G$,so I can see one of the inclusions, but I don't see why $G \subset \coprod gen(C)$, maybe I am not understanding what $gen(C)$ is, I interpret it as $gen(C)=\{g \in G : <g>=C\}$, if $c \in C$, then $c=g^k$ for some $k$, but this doesn't imply that $c \in \{g \in G : <g>=C\}$, so what $gen(C)$ is as a set?

I hope it is clear what my doubt is, I would appreciate if someone could clear this up to me.

• $\operatorname{gen} (C)$ is the set of generators of the subgroup $C$ of $G$. Since every element of $G$ generates some (cyclic) subgroup of $C$, you have $G \subset \coprod_{C \leqslant G} \operatorname{gen} (C)$. – Daniel Fischer Sep 27 '14 at 20:45

A function $f$ from the positive integers to the positive integers (or to any semigroup, really) is called multiplicative if $\gcd(a,b)=1$ implies $f(ab) = f(a) f(b).$
Given any such $f,$ one may prove without trouble that $$g(n) = \sum_{d|n} f(d)$$ is multiplicative in the same sense. As a result, it suffices to check any relation on primes and prime powers. $$1 + (p-1) = p,$$ $$1 + (p-1) + (p^2 - p) = p^2,$$ $$1 + (p-1) + (p^2 - p) + (p^3 - p^2)= p^3,$$ and so on.
It might be the case Rotman means to consider the set of generators of subgroups of $G$. Let me give an example. Take the group $C_{21}=\{1,\ldots,g^{20}\}$. The generators of the trivial groups are $1$, of the cyclic subgroup of size $7$, $g^k$ such that $k<21$ and $21/(k,21)=7$, i.e. such that $(k,21)=3$, i.e. such that $(k,7)=1$ and $3\mid k$. These are $g^3,g^6,g^9,g^{12},g^{15},g^{18}$. The generators of the cyclic subgroup of size $3$ are similarily those $k<21$ such that $(k,3)=1$ and $7\mid k$, so $g^7,g^{14}$, and finally the generators of $G$ itself which are $g,g^2,g^4,g^5,g^8,g^{10},g^{11},g^{13},g^{16},g^{17},g^{19},g^{20}$.
The tally is thus that $$21=1+2+6+12=\varphi(21/21)+\varphi(21/7)+\varphi(21/3)+\varphi(21/1)$$
The point here is that for $C_n$; the cyclic subgroup of order $d\mid n$ has exactly $\varphi(n/d)$ generators.