0

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...

PCeltide
  • 1,534
  • There is a typo in the first highlighted section: "... for any $d|C_n$..." should be "...for any $d|n$..." – DanielWainfleet Oct 09 '19 at 10:17
  • Done! I noticed it too while reading, forgot to edit it out – PCeltide Oct 09 '19 at 10:31
  • 1
    For each $g\in C_n$ there is exactly one divisor $k,$ of $n$, such that $g\in A_k,$ by def'n of $A_k.$ So the number of members of $C_n$ (which is $n$) is the sum of the numbers of members of all the $A_k,$ over all the $k$ that divide $n$. That is, $n=|C_n|=\sum_{k|n}|A_k| .$ If this is still not clear, suppose $C_n$ is the set of all players in a hockey league and the set of teams is ${T_k:k|n}$ and $A_k$ is the set of players on team $T_k$........And by def'n of the notation, $\sum_{g\in C_n}1$ is the number of members of $C_n.$ ("Count $1$ for each $g\in C_n$"). – DanielWainfleet Oct 09 '19 at 10:54

1 Answers1

2

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)$

gandalf61
  • 15,326