# Difficulty understanding the proof that $n=\sum_{d|n} \phi(d)$

I am reading the proof of $$n = \sum_{d|n} \phi(d)$$ where $n$ is any positive integer and $\phi$ is the Euler's $\phi$ function .

Now the proof goes on like this .

An arbitrary group $G$ of order $n$ is taken and the equivalence relation is introduced as follows $$x\equiv y \ \ \ \iff\ \ \ (x) = (y)$$ where $(x)$ is the cyclic group generated by $x$ and denote by $G(x)$ the equivalence class of $x$. Then $G$ is the disjoint union $$G = \cup_{x\ in G} G(x)$$

Then $$n = |G| = \sum |G(x)|$$ Up to this is alright. I don't understand what they did after this. Next they simply write "If $G$ has order $n$ , then counting gives $n = \sum |G(x)| = \sum_{d|n} \phi (d)$ where the summation ranges over all cyclic groups of $G$, while if $G$ is cyclic then this result is obtained from the lemma 'A finite cyclic group $G$ has a unique subgroup of order of every divisor of $|G|$ ' "

Thanks.

• That's a lot of words. Is there a particular part of what they wrote that you don't understand? Or are you more confused about why this leads to the conclusion? Are you familiar with the lemma? Sep 13 '15 at 20:13
• The disjoint union symbol is being abused here. The union only becomes disjoint if you throw away repeated entries. Sep 13 '15 at 20:24
• @ErickWong : I clearly mentioned which part I do not understand ; the part within the double quotes, the whole of that. Sep 13 '15 at 20:27
• possible duplicate of this question, and possibly many others.
– robjohn
Sep 13 '15 at 23:51

So we need to prove: $|G(x)| = \phi(d)$, whereas $d = o(x)$, i.e $x^d = e$, and $d$ is the order of $x$ in $G$, and by definition of $|G(x)| = |\{y\in G: \exists k, 0\leq k \leq d, y = x^k\}|=|\{k: 0 \leq k \leq d, (k,d) = 1\}| =\phi(d) \Rightarrow |G(x)|= \phi(d)$, thus we're done.
I think it might help to take a concrete group and work through what the $G(x)'s$ are explicitly.
Another proof I like is : Look at the set $\{\frac kn | 1\leq k \leq n\}$ and group the elements by what their denominators are in reduced form.