How many elements of order $k$ are there in $\mathbb{Z} / p \mathbb{Z}^{*}$?
Let $x$ be a generator of $\mathbb{Z} / p \mathbb{Z}^{*}$ (the result of the exercise implies the existence of a generator, so unless we want to reprove everything, we will have to use this result). The elements of $\mathbb{Z} / p \mathbb{Z}^{*}$ are therefore the $x^{k}$ with $k$ between 0 and $p-2$. What is the order of such an $x^{k}$? It is the smallest $a$ such that $ak$ is a multiple of $p-1$, so it is $\frac{\operatorname{LCM}(p-1, k)}{k}$, which is $\frac{p-1}{\operatorname{GCD}(p-1, k)}$. Let $d$ be a divisor of $p-1$. The element $x^{k}$ is of order $\frac{p-1}{d}$ if and only if $\operatorname{GCD}(p-1, k)=d$, hence if $k$ is of the form $\alpha d$ with $\alpha$ coprime with $\frac{p-1}{d}$. There are $\phi\left(\frac{p-1}{d}\right)$ such $k$.

Two remarks: the notion of order also works in $(\mathbb{Z} / n \mathbb{Z},+)$, the order of $x$ being the smallest integer $n$ such that $n x$ is zero (where $n x$ is defined as $x+x+\ldots+x$ $n$ times). An identical reasoning shows that, for $d$ dividing $n$, there are $\phi(d)$ elements of order $d$ (morally, our proof consisted in, via the choice of a generator, placing ourselves in $(\mathbb{Z} /(p-1) \mathbb{Z},+)$. We deduce by counting the elements of $\mathbb{Z} / n \mathbb{Z}$ according to their order, the very nice, and important, combinatorial identity:

$$
\phi(\mathfrak{n})=\Sigma_{\mathrm{d} \mid \mathfrak{n}} \phi(\mathrm{d})
$$