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

Let $p>2$ be a prime number, and $y$ be an element of order $d$ in $(\mathbb{Z}/p\mathbb{Z})^\times$, $d \in \mathbb{N}$. I already know that $x^d \equiv 1 \mod p$ has $d$ solutions. Then how to show that every element of order $d$ is one of the $\varphi(d)$ generators of the group generated by $y$?

-
Looking through your question history I noticed that you tag every question with the analytic-number-theory tag. That tag is not relevant to many of your questions (including this one). Please use tags that describe the topic of your question. –  Brandon Carter Nov 3 '11 at 1:48
Sorry, I will be careful next time! –  Rob Nov 3 '11 at 1:52

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