I've just read in Rotman's group theory textbook the proof of the following 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.

  • 1
    $\begingroup$ $\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)$. $\endgroup$ – Daniel Fischer Sep 27 '14 at 20:45

Probably gives that proof because the book is on group theory.

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.

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.