Hey so I was searching for Gauss's proof of the Euler Totient function property and I found an answer but I had a problem understanding it:
Consider the cyclic group $C_n$. Then, for every $g\in C_n$, $o(g)$ divides $|C_n|=n$. Moreover, for any $d|n$, $\exists g\in C_n:o(g)=d$. Thereofore, if $A_k$ is the set of all the elements of $C_n$ with order $k$, $A_k \neq \emptyset \Longleftrightarrow k | n$. Therefore, $\{A_k : k | n\}$ is a partition of $C_n$. So: $$|C_n|= n = \displaystyle{\sum _{g \in C_n}} 1 = \displaystyle{\sum _{d|n} |A_d|} = \displaystyle{\sum _{d|n} \varphi(d)}$$ Since the number of elements of order $d$ in $C_n$ is $\varphi(d)$.
What I didn't understand was why the number of elements with an order d in cyclic group, of an order $n$, is $\phi(d)$. Also, I couldn't undertand why he could write this:
$\displaystyle{\sum _{g \in C_n}} 1 = \displaystyle{\sum _{d|n} |A_d|}$
Please help! I've been trying to undertand the proof for a day now...
The proof is simply counting the number of elements of $C_n$ in two different ways.
We know there are $n$ elements of $C_n$, and we know that the sets $A_d=\{g \in C_n | o(g)=d\}$ partition $C_n$ i.e. each $g\in C_n$ is a member of one and only one $A_d$. And we know that $|A_d|=0$ unless $d$ is a factor of $n$. So
$\displaystyle \sum_{d|n}|A_d| = n$
To see why $|A_d| = \varphi(d)$, think of the elements of $C_n$ as being powers of a generator $a$, so $C_n=\{a, a^2, a^3, \dots, a^n\}$. If $e=\frac{n}{d}$ then $a^e$ will have order $d$ and each of the $d$ powers of $a^e$ in $\{a^{ke}| 1 \le k \le d \}$ will also have order $d$ unless $\gcd(k,d) > 1$. So
$|A_d| = |\{k|1\le k \le d, \gcd(k,d)=1\}| = \varphi(d)$