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

  • 0
    Sorry, I will be careful next time!2011-11-03

2 Answers 2

2

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

2

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

  • 0
    Except for the proof of the first equality, this proof appears in Weil's gem *Number theory for beginners* and in several other books.2011-11-03