7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bzc
    Nov 3, 2011 at 1:48
  • $\begingroup$ Sorry, I will be careful next time! $\endgroup$
    – Rob
    Nov 3, 2011 at 1:52

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Except for the proof of the first equality, this proof appears in Weil's gem Number theory for beginners and in several other books. $\endgroup$
    – lhf
    Nov 3, 2011 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .