Order Modulo n of Power of Integer

Theorem

Let $a$ have order $c$ modulo $n$.

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

Corollary

If $a$ is a primitive root of $n$, then $a^k$ is also a primitive root of $n$ iff $k \perp \phi \left({n}\right)$ where $\phi$ is the Euler phi function.

Furthermore, if $n$ has a primitive root, it has exactly $\phi \left({\phi \left({n}\right)}\right)$ of them.

Proof

Let $a$ have order $c$ modulo $n$.

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

Let $c = d c'$ and $k = d k'$ where $\gcd \left\{{c', k'}\right\} = 1$ from Divide by GCD for Coprime Integers.

We want to show that the order $a^k$ modulo $n$ is $c'$.

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

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({a^k}\right)^{c'}\)	\(=\)	\(\displaystyle \left({a^{dk'} }\right)^{c/d}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a^{k'c}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a^c}\right)^{k'}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle \left({1}\right)^{k'}\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, n}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle 1\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, n}\right)\)	\(\displaystyle \)

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

On the other hand, $a^{kr} = \left({a^k}\right)^{r} \equiv 1 \left({\bmod\, n}\right)$, and so $kr$ is a multiple of $c$.

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

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

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

$\blacksquare$

Proof of Corollary

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

Then $R = \left\{{a, a^2, \ldots, a^{\phi \left({n}\right)}}\right\}$ is a reduced residue system for $n$, and so all primitive roots are contained in this set.

The order $a^k$ modulo $n$ is $\dfrac {\phi \left({n}\right)} {\gcd \left\{{\phi \left({n}\right), k}\right\}}$.

Hence $a^k$ will be a primitive root of $n$ exactly when $\gcd \left\{{\phi \left({n}\right), k}\right\} = 1$, i.e. when $\phi \left({n}\right) \perp k$.

So the primitive roots are the integers $a^k$, where $k$ is in the set $\left\{{1, 2, \ldots, \phi \left({n}\right)}\right\}$.

By definition of $\phi$, there are $\phi \left({\phi \left({n}\right)}\right)$ such exponents $k$.

Hence there are $\phi \left({\phi \left({n}\right)}\right)$ primitive roots of $n$.

$\blacksquare$