Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
Except for the proof of the first equality, this proof appears in Weil's gem Number theory for beginners and in several other books. – lhf Nov 3 '11 at 2:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.