mathschallenge.net

Problem

If $p$ is prime and $GCD(a, p) = 1$, we know by Fermat's Little Theorem that $a^{p-1} \equiv 1 \mod p$.

Consider $3^k \mod 7$:

$\begin{align}3^1 &\equiv 3\\3^2 &\equiv 2\\3^3 &\equiv 6\\3^4 &\equiv 4\\3^5 &\equiv 5\\3^6 &\equiv 1\end{align}$

However, $p - 1$ is not necessarily the least value of $k$ for which the residue is one. For example, $2^k \mod 7$:

$\begin{align}2^1 &\equiv 2\\2^2 &\equiv 4\\2^3 &\equiv 1\\2^4 &\equiv 2\\2^5 &\equiv 4\\2^6 &\equiv 1\end{align}$

We call $k = ord(a, p)$ the least value for which $a^k \equiv 1 \mod 7$; for example $ord(3, 7) = 6$ and $ord(2, 7) = 3$.

Prove that $p - 1$ is always a multiple of $ord(a, p)$.