Proving if $g$ is a primitive root $\pmod n$ and $n$ is prime, then $g^k$ $\pmod n$ is also a primitive root if and only if $\gcd(k, n-1) = 1$

Question

Prove that when $n$ is prime, and $g$ is a primitive root $\pmod n$, $g^k$ $\pmod n$ is always a primitive root whenever $\gcd(k, n-1)$ $=$ $1$.

Known Facts:

• It would be the case that if $\gcd(k, n-1)$ $=$ $q$, then there are $(n-1)/q$ $q^{th}$ power residues
• There are $ϕ$($n-1$) primitive roots $\pmod n$ if $n$ is prime.
• There is always a solution $a$ to $a^k$ $=$ $g$ $\pmod n$ whenever $\gcd(k, n-1)$ $=$ $1$ and $n$ is prime ($g$ is any integer).
• There is always a solution $k$ to $a^k$ $=$ $g$ $\pmod n$ whenever $a$ is a primitive root $\pmod n$ (by definition)

Can anyone complete the proof for the statement above using the known facts? Thanks in advance.

Answer 1

You have to show that the subroup generated by $g^k$ contains $g$, remark that little fermat implies that $g^{n-1}=1$. Write $ak+b(n-1)=1$, you obtain $g=g^{ak+b(n-1)}=(g^k)^a$.