Let $p$ be some odd prime. Let $r$ be the smallest natural number such that $x^r \equiv 1 \pmod{p}$ for some $x \in \mathbb{F}_p^{\times}$.
Prove that such an $r$ exists, and that it divides $(p-1)$.
My thoughts: that it exists seems trivial. The field is finite, so all elements must have some finite order? Not sure how to state this rigorously though. For $r \mid (p-1)$ I'm thinking Lagrange's theorem seems an obvious choice. Guidance appreciated.
Best Answer
One way is to use the division theorem. Write $p-1 = qr + s$ where $q\in \mathbb Z$ and $0\le s <r$. We want to use the fact that $r$ is minimal to deduce that $s=0$, and hence that $r\mid p-1$.
By Fermat's little theorem, $x^{p-1} \equiv 1 \pmod p$. By assumption, $x^{r} \equiv 1 \pmod p$ and hence $x^{qr} \equiv 1 \pmod p$, so $x^{p-1 - qr} \equiv 1 \pmod p$. Can you finish from here?
Alternatively, you can work group theoretically: what is the order of the subgroup $\langle x\rangle \le \mathbb F_p^\times$? What can you deduce about its order?