Recall that the order of \(a \pmod{m}\) is the smallest positive integer \(h\) such that
$$
\begin{align*}
a^h \equiv 1 \pmod{m}
\end{align*}
$$
Based on this, we have the following theorem
Theorem (7.2 in Andrews)
If \(a\) has order \(h\) modulo \(m\). Then,
$$
\begin{align*}
a^r \equiv 1 \pmod{m}
\end{align*}
$$
Then \(h \mid r\).
Proof
Let \(a\) be an element of order \(h\) modulo \(m\). Suppose
$$
\begin{align*}
a^r \equiv 1 \pmod{m}
\end{align*}
$$
By the divison algorithm write
$$
\begin{align*}
r = kh + s \quad (0 \leq s < h)
\end{align*}
$$
Then
$$
\begin{align*}
a^{r} \equiv a^{kh + s} \equiv a^{kh} \cdot a^s \equiv a^s \pmod{m}
\end{align*}
$$
But \(h\) is the smallest integer such that \(a^h \equiv 1 \pmod{m}\) and \(s < h\). Thus, \(s = 0\). Therefore, \(h \mid r\). \(\ \blacksquare\)
References
- Number Theory by George E. Andrews