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.
On
Typically when you are asked to prove something that seems obvious, proofs by contradiction can really come in handy. Think about what it would mean if there were no smallest $r\in \mathbb{N}$ such that $x^r \equiv 1 modp$?
The second portion seems like something that might contradict a theorem of Fermat if it were not true ;). (Hint: it's not his big theorem).
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?