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.

  • $\begingroup$ This : en.wikipedia.org/wiki/Fermat's_little_theorem will help you. $\endgroup$ – Peter Oct 25 '15 at 21:56
  • $\begingroup$ $\mathbf F_p^\times$ is a multiplicative group and $r$ is the order of the subgroup generated by $x$. $\endgroup$ – 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$?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.