Past exam of the mathematics course of the University of Cambridge / 2001 / ia / Paper 4 / 7E / b / Solution

Let $d$ be the multiplicative order of $a$ modulo $p$. Use Euclidean division to write $x=qd+r$, $0\le r<d$. Since $a^d\equiv 1$,If $a^x\equiv 1$, minimality of $d$ forces $r=0$, so $d$ divides $x$. Conversely, $d\mid x$ immediately gives $a^x\equiv 1$. For negative integers $x$, powers are interpreted using the multiplicative inverse and the same argument applies.

Apply the result to $x=p-1$, using Fermat's little theorem. Then $d\mid p-1$, equivalently