A question about the proof that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic

Hint: $x^d-1$ has at most $d$ roots and $y,y^2, \dots, y^d=1$ are are all distinct roots of this polynomial. But any element $x$ of order $d$ is also a root of this polynomial, so $x \in \langle y \rangle$. Since $x$ has order $d$, $\langle x \rangle = \langle y \rangle$.

This usually goes like this. Let $\psi(d)$ be the number of elements of order $d$. Then, as you have noticed, $\phi(d) \le \psi(d)$. Then $p-1=\sum_d \phi(d) \le \sum_d \psi(d) =p-1$ implies $\phi(d) = \psi(d)$ for all $d$. The first equality comes from considering the proper fractions with denominator $p-1$ and their reduced forms. The second equality comes from Lagrange's theorem: every element has an order and it has to be a divisor of $p-1$.