The order modulo p divides p − 1

Statement

Let $p$ be a prime number, and let $a$ be an integer with $p \nmid a$. Then the multiplicative order of $a$ modulo $p$ divides $p - 1$.

Remarks

The proof: $a^{p-1} \equiv 1 \pmod p$ by Fermat's little theorem, and each exponent $m$ with $a^m \equiv 1$ is a multiple of the order. The order is equal to $p - 1$ exactly when $a$ is a primitive root modulo $p$. For example, modulo $13$, the order of $3$ is $3$ and the order of $2$ is $12$. Both divide $12$.

Explanations

L1 human

The powers of $a$ modulo $p$ go round a cycle. The length of the cycle always divides $p - 1$. Modulo $11$, the powers of $5$ are $5, 3, 4, 9, 1$. The cycle has length $5$, and $5 \mid 10$.