Order Modulo n of Power of Integer

Theorem

Then for any $k \ge 1$, $a^k$ has multiplicative order $\dfrac c {\gcd \set {c, k}}$ modulo $n$.

Let $a$ be a primitive root of $n$.

Then:

$a^k$ is also a primitive root of $n$

$k \perp \map \phi n$

where $\phi$ is the Euler phi function.

Furthermore, if $n$ has a primitive root, it has exactly $\map \phi {\map \phi n}$ of them.

Consider $a^k$ and let $d = \gcd \set {c, k}$.

Let $c = d c'$ and $k = d k'$ where $\gcd \set {c', k'} = 1$ from Integers Divided by GCD are Coprime.

Let the order $a^k$ modulo $n$ be $r$.

Then:

$\ds \paren {a^k}^{c'}$

$=$

$\ds \paren {a^{d k'} }^{c/d}$

$\ds $

$=$

$\ds a^{k' c}$

$\ds $

$=$

$\ds \paren {a^c}^{k'}$

$\ds $

$\equiv$

$\ds \paren 1^{k'}$

$\ds \pmod n$

$\ds $

$\equiv$

$\ds 1$

$\ds \pmod n$

So, by Integer to Power of Multiple of Order, $c'$ is a multiple of $r$, that is, $r \divides c'$.

On the other hand, $a^{k r} = \paren {a^k}^r \equiv 1 \pmod n$, and so $k r$ is a multiple of $c$.

Substituting for $k$ and $c$, we see that $d k' r$ is a multiple of $d c'$ which shows $c'$ divides $k' r$.

But from Euclid's Lemma (which applies because $\gcd \set {c', k'} = 1$), we have that $c'$ divides $r$, or $c' \divides r$.

So, as $c' \divides r$ and $r \divides c'$, from Divisor Relation on Positive Integers is Partial Ordering, it follows that $c' = r$.

$\blacksquare$