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|$ ' "

Please help me with explanation of this last segment of the proof.


  • $\begingroup$ 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? $\endgroup$
    – Erick Wong
    Sep 13 '15 at 20:13
  • $\begingroup$ The disjoint union symbol is being abused here. The union only becomes disjoint if you throw away repeated entries. $\endgroup$ Sep 13 '15 at 20:24
  • $\begingroup$ @ErickWong : I clearly mentioned which part I do not understand ; the part within the double quotes, the whole of that. $\endgroup$
    – user118494
    Sep 13 '15 at 20:27
  • $\begingroup$ possible duplicate of this question, and possibly many others. $\endgroup$
    – 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.

Slightly offtopic:

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.


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.