0
$\begingroup$

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.

$\endgroup$
1
  • 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, 2016 at 21:06

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .