Exercise 1138Number theory › PrimesL1Added 3 Nov 2026

Order modulo a prime

#order#prime#divisor

Statement

Let $p$ be prime and $a$ coprime to $p$ . Show that the order of $a$ mod $p$ divides $p-1$ .

Hint

Fermat: $a^{p-1}\equiv1\pmod p$ . Use the division of $p-1$ by the order.

Show solutionHide solution

Setup. Let $k=\operatorname{ord}_p(a)$ and write $p-1=qk+r$ with $0\le r<k$ .

Compute. $1\equiv a^{p-1}=a^{qk+r}\equiv a^r\pmod p$ .

Minimality. By minimality of $k$ , $r=0$ , so $k\mid p-1$ .

Conclusion. The order of any element of $\mathbb{F}_p^*$ divides $p-1$ .