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.

  • 1
    $\begingroup$ How do you define primitive root? Also your known facts are a little confusing. For example in 3rd one, is $a$ or $g$ primitive root? $\endgroup$ – iamvegan Oct 9 '16 at 21:06

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.