Proof That the Order of a^k Equals the Greatest Common Divisor or Irder of a and k
If
\[a\]
has order \[c\]
modulo \[n\]
then for any \[k \ge 1\]
, \[a^k\]
has order \[\frac{c}{gcd(c,k)}\]
modulo n.Proof
Suppose that
\[a\]
has order \[c\]
modulo n. Consider \[a^k\]
. Let \[d=gcd(k,c)\]
then \[c=c'd, \; k=k'd\]
for some integers \[c', \; k', \; gcd(c',k')=1\]
.Suppose the order of
\[a^k\]
is \[r\]
. Then\[(a^k)^{c'}=(a^{dk'})^{c/d}=a^{k'c}=(a^c)^{k'} \equiv 1 \; (mod \; n)\]
Then
\[c\]
is a multiple of \[r\]
.On the other hand
\[a^{kr}=(a^k)^r \equiv 1 \; (mod \; n)\]
.So
\[kr\]
is a multiple of \[c\]
, \[dk'r\]
is a multiple of \[dc'\]
then \[c'\]
divides \[k'r\]
. Euclid's Lemma tells us \[c'\]
divides \[r\]
(since \[gcd(c'.k')=1\]
.As
\[c'\]
is both a multiple and divisor of \[r\]
it must be that \[c'=r'\]
.A copnsequence is that if
\[a\]
is a primitive root of \[n\]
so that the order of \[a\]
is Euler's Totient Function \[\phi (n)\]
, then so is \[a^k\]
as long as \[gcd(k, \phi (n))=1\]
. 
