Number of order 5 elements in $(\mathbb{Z}/31\mathbb{Z})^{\times}$ I know there are $4$ elements of order $5$ and the elements are $\bar{2}$,$\bar{4}$,$\bar{8}$,$\bar{16}$. I was only able to show it by using brute force. Eg. I found that the element $\bar{2}$ has order $5$ by calculating $2^5=32 \equiv 1 \ \text{mod} \ 31$.
Is there a smarter way to find the number of elements of order $k \in \mathbb{N}$ in a finite multiplicative group?
 A: The multiplicative group of the finite field $\mathbb Z/p\mathbb Z$ is cyclic. Note that it has order $p-1$ and that every element of the group satisfies $p(x)=x^{p-1}-1=0$ in the field. Because we are working in a field, a polynomial of degree $n$ has at most $n$ distinct roots. Hence the elements of the multiplicative group are precisely the roots of this equation.
If $q$ is a factor of $p-1$ then the elements of order $q$ satisfy $q(x)=x^q-1=0$ - there can be at most $q$ of them for the same reason, and in fact there are exactly $q$ distinct roots, which can be proved by counting - though a root may have order which is a smaller  factor of $q$. If $q$ is prime, then there are $q-1$ elements of precise order $q$ (the element $1$ has order $1$).
The observation that the group is cyclic also allows us to use the fact that a cyclic subgroup has precisely one subgroup of each order which is a factor of the order of the group.
A: If $G$ is a cyclic group of order $n$ and if $k$ is a positive integer that divides $n$ then the number of elements of order $k$ equals $\varphi{(k)}$ where $\varphi$ is the Euler's phi-function.
