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$