Wednesday, 8 April 2026

Exercise (6.1).10

Prove that if $a$ modulo $n$ has order $mk$ where $m, k$ are positive integers then $a^m$ has order $k$.


We're given $mk$ as the order of $a$ modulo $n$. This means

$$ a^{mk} \equiv 1 \pmod n $$

Rewriting

$$ (a^{m})^{k} \equiv 1 \pmod n $$

This is a necessary for $k$ to be the order of $a^m$, but not sufficient. 

We also need to show that $k$ is the smallest positive integer such that $(a^m)^k \equiv 1 \pmod n$. 

For the purpose of contradiction, let's assume $j<k$ is the order of $a^m$ modulo $n$. That would mean

$$ (a^m)^j \equiv 1 \pmod n $$

That is

$$ a^{mj} \equiv 1 \pmod n $$

Here $mj < mk$ which is not possible because we're given $mk$ as the order of $a$, and so $mk$ is the least positive integer such that $a^{mk} \equiv 1 \pmod n$.


We have shown that if $a$ modulo $n$ has order $mk$ where $m, k$ are positive integers, then $a^m$ has order $k$.