Proof that the order modulo p divides p − 1

Proof

1. Let $p$ be a prime number and let $a$ be an integer with $p \nmid a$.
2. The only positive divisors of $p$ are $1$ and $p$, and $p \nmid a$. So $\gcd(a, p) = 1$, and $a$ is coprime to $p$.
3. So the multiplicative order $k = \operatorname{ord}_p(a)$ is defined. It is the least positive integer with $a^k \equiv 1 \pmod p$.
4. By Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$.
5. By the division algorithm, there are integers $q$ and $r$ with $p - 1 = qk + r$ and $0 \le r < k$. Here $q \ge 0$, because $p - 1 \ge 0$ and $r < k$.
6. Then $a^{p-1} = (a^k)^q \cdot a^r$. Since $a^k \equiv 1$, powers and products of congruences give $a^{p-1} \equiv 1^q \cdot a^r = a^r \pmod p$.
7. With step 4 this gives $a^r \equiv 1 \pmod p$.
8. If $r > 0$, then $r$ is a positive integer less than $k$ with $a^r \equiv 1 \pmod p$. This contradicts the minimality of $k$.
9. So $r = 0$, and $p - 1 = qk$. Hence $\operatorname{ord}_p(a)$ divides $p - 1$.