# Show that multiplicative order mod p exists and that it divides (p-1)

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.

• This : en.wikipedia.org/wiki/Fermat's_little_theorem will help you. – Peter Oct 25 '15 at 21:56
• $\mathbf F_p^\times$ is a multiplicative group and $r$ is the order of the subgroup generated by $x$. – Bernard Oct 25 '15 at 21:58

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