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.