## Order Of A Prime

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

#### Solution

By definition $k = ord(a, p)$ is the least value for which $a^k \equiv 1 \mod p$, and by FLT we know that $k \le p - 1$.

Let $p - 1 = bk + r$, where $0 \le r \lt k$.

If $r = 0$ then we are done, as $p - 1$ is a multiple of $k$, but for $r \gt 0$, $k$ will not a multiple of $p - 1$.

$\therefore a^{p-1} = a^{bk+r} = a^{bk} a^r$.

But $a^{bk} = (a^k)^b \equiv 1$, because by definition $a^k \equiv 1$.

Hence $a^{p-1} \equiv a^r \equiv 1$.

However, $r \lt k$, and by definition $k$ is the least value for which the residue is one. So we conclude that $r = 0$, and we prove that $p - 1$ is a multiple of $k = ord(a, p)$.