= 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\equiv1$,
$$
a^x\equiv a^r\pmod p.
$$
If $a^x\equiv1$, minimality of $d$ forces $r=0$, so \b[$d$ divides $x$]. Conversely, $d\mid x$ immediately gives $a^x\equiv1$. 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
$$
\boxed{p\equiv1\pmod d.}
$$
Back to article page
