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*} $$

We also showed here that if \(a\) has order \(h\) modulo \(m\), and \(a^r \equiv 1 \pmod{m}\), then \(h \mid r\). Next we have the following theorem

Theorem (7.4 in Andrews)
If \(a\) has order \(h\) modulo \(m\). Then \(a^k\) modulo \(m\) has order $$ \begin{align*} |a^k| = \frac{h}{\gcd(h,k)} \end{align*} $$

Proof 1

Let \(a\) be an element of order \(h\) modulo \(m\). Consider \(a^k\). The order of \(a^k\) is the smallest integer \(j\) such that

$$ \begin{align*} (a^k)^j = a^{kj} \equiv 1 \pmod{m} \end{align*} $$

But since \(a\) has order \(h\). Then we know that we must have \(h \mid kj\) (Proof Here). Now,

$$ \begin{align*} h &\mid kj \\ \frac{h}{\gcd(h,k)} &\mid \frac{k}{\gcd(h,k)}j \end{align*} $$

Clearly \(\gcd(\frac{h}{\gcd(h,k)},\frac{k}{\gcd(h,k)}) = 1\). Therefore, we must have that

$$ \begin{align*} \frac{h}{\gcd(h,k)} \mid j \end{align*} $$

Furthermore, observe that

$$ \begin{align*} (a^k)^{\frac{h}{\gcd(h,k)}} \equiv (a^h)^{\frac{k}{\gcd(h,k)}} \equiv 1^{\frac{k}{\gcd(h,k)}} \equiv 1 \pmod{m} \end{align*} $$

But \(j\) is the smallest integer such that \((a^k)^j \equiv 1 \pmod{m}\). Then we must also have that

$$ \begin{align*} j \mid \frac{h}{\gcd(h,k)} \end{align*} $$

Therefore,

$$ \begin{align*} j = \frac{h}{\gcd(h,k)} \end{align*} $$

Proof 2 (class/Andrews)

Let \(h\) be the order of \(a\) and let \(j\) be the order of \(a^k\). Let

$$ \begin{align*} h' = \frac{h}{\gcd(h,k)} \quad \text{ and } \quad k' = \frac{k}{\gcd(h,k)} \end{align*} $$

We will show that \(j = h'\) by showing that \(j \mid h'\) and that \(h' \mid j\).
\(j \mid h'\): Observe that since \(a\) has order \(h\), then

$$ \begin{align*} (a^k)^{h'} \equiv a^{kh'} \equiv a^{\frac{hk}{\gcd(h,k)}} \equiv (a^h)^{k'} \equiv 1 \pmod{m} \end{align*} $$

But by this fact, this means that \(j \mid h'\).

\(h' \mid j\): Since the order of \(a^k\) is \(j\), then

$$ \begin{align*} (a^k)^{j} \equiv a^{kj} \equiv 1 \pmod{m} \end{align*} $$

But we know that \(a\) has order \(h\) so this implies that \(h \mid kj\). This means that

$$ \begin{align*} ha = kj \quad \text{ for some $a \in \mathbb{Z}$ } \end{align*} $$

If we divide by \(\gcd(h,k)\), then

$$ \begin{align*} h'a = k'j \end{align*} $$

Note that \(\gcd(h',k') = 1\). Thus, \(h'\) must divide \(j\) as we wanted to show. Therefore, \(a^k\) has order \(j = h' = \frac{h}{\gcd{h,k}}\) as desired. \(\ \blacksquare\)

References