Prove the number of elements of order $n$ in $\mathbb{Z}_n$ is $\phi (n)$ Prove the number of elements of order $n$ in $\mathbb{Z}_n$ is $\phi (n)$, where $\phi (n)$ is the Euler Totient Function.
The hint for this problem says "You need to decide which $[a] \in \mathbb{Z}_n$ generate $\mathbb{Z}_n$"
I'm having difficulty getting started. Even just knowing where exactly to begin.

What I know

*

*I know that the Euler Totient Function is given by $$\phi (n) = (p_1 - 1)p_1^{r_1 - 1} \cdots (p_k - 1)p_k^{r_k - 1}$$
where $n \in \mathbb{Z}$ has prime factorization $$n = p_{1}^{r_1} \cdots p_{k}^{r_k}$$


*The order of an element is $$\lvert [a] \rvert = n$$ Where $n$ is the smallest positive integer such that $[a]^{n} = [0] \equiv e$
So far, the only fact we have come across to elucidate the possible generators of $\mathbb{Z_n}$ is the following theorem:

For any $n \geq 2$, if $H < \mathbb{Z_n}$ is a subgroup, then there exists a positive divisor, $d$, of $n$ such that $$H = \langle [d] \rangle$$ Furthermore, this defines a bijection between the divisors of $H$ and the subgroups of $\mathbb{Z_n}$. Furthermore, if $d,d' > 0$ are $2$ divisors of $n$, then $\langle [d] \rangle < \langle [d'] \rangle$ iff $d' \mid d$



*In other words, the generators of any subgroup of $\mathbb{Z_n}$ (and hence, $\mathbb{Z_n}$ itself) must be divisors of $n$, i.e., the elements $[a] \in \mathbb{Z_n}$ such that $n = ka$ for $k \in \mathbb{Z}$.

*

*However, just using, say, $\mathbb{Z_6}$ as an example we know that $2$ is a divisor for $6$, but $2$ doesn't generate $\mathbb{Z_6}$ since $\langle [2] \rangle = \{[2], [4], [0] \}$. So I see that just because $2$ is a divisor of $6$ and $\mathbb{Z_6}$ is a subgroup of $\mathbb{Z_6}$ that doesn't necessarily mean that $2$ generates $\mathbb{Z_6}$. The Theorem is just saying that for each subgroup of $\mathbb{Z_n}$ there exists at least $1$ generator.

*Okay, so to that end, would I just use $[1]$ as the generator for $\mathbb{Z_n}$? Since $\mathbb{Z_n}$ is a general group and $[1]$ is a generator for any such group, doesn't matter what value $n$ takes. How would I substantiate this beyond just saying that $[1]$ is a generator for any $\mathbb{Z_n}$ whereas $[a]$ where $a \mid n$ may or may not be a generator for the particular subgroup $\mathbb{Z_n}$ of $\mathbb{Z_n}$ based on the above theorem?




As I mentioned above I'm having difficulty seeing where I should start with this problem. As well as just consolidated all of the information and seeing where it ties together to start following a thread. So, any guidance in that regard would be very much appreciated.
 A: This follows from, ultimately, the following

Fundamental Theorem of Cyclic Groups: Every subgroup of a cyclic group is cyclic. Also, if $|\langle a\rangle|=n$, then the order of any subgroup of $\langle a\rangle$ divides $n$; moreover, for each divisor $k$ of $n$, then group $\langle a\rangle$ has exactly one subgroup of order $k$ - namely, $\langle a^{n/k}\rangle$.

A proof can be found here. It is also Theorem 4.3 of Gallian's "Contemporary Abstract Algebra (Eighth Edition)".

Theorem:
If $d$ is a positive divisor of $n$, the number of elements of order $d$ in
a cyclic group of order $n$ is $\varphi(d).$

This is Theorem 4.4 of Gallian's book.
Proof: By the above, the group has exactly one subgroup of order $d$; call it $\langle a\rangle$. Then each element of order $d$ generates this subgroup and (since $\langle a^i\rangle=\langle a^j\rangle$ iff $\gcd(|a|, i)=\gcd(|a|, j)$) an element $a^k$ generates $\langle a\rangle$ iff $\gcd(k,d)=1$. The number of these elements is exactly $\varphi(d)$. $\square$
A: The "What I know" about the $\phi$ function is rather a lemma following from the definition of $\phi$, but this latter only is what you need here:
$$\phi(n):=\#\{k\in\{1,\dots,n-1\}\mid\gcd(k,n)=1\}$$
In fact, the order of $[k]\in\Bbb Z_n$ is by definition the least positive integer $m$ such that $mk=nl$, for some integer $l$. So, $m$ is of the form $n/(k/l)$ $(*)$, and hence the least one is gotten when the denominator in $(*)$ is the greatest divisor of $k$, which is also a divisor of $n$, namely:
$$o([k])=\frac{n}{\gcd(k,n)}$$
Therefore, $o([k])=n\iff\gcd(k,n)=1$, whence:
\begin{alignat}{1}
\#\{[k]\in\Bbb Z_n\mid o([k])=n\} &= \#\{k\in\{1,\dots,n-1\}\mid \gcd(k,n)=1\} \\
&= \phi(n)
\end{alignat}
