I haven't fully wrapped my head around primitive roots yet and I have a question with them:

Let $p$ be an odd prime and $g$, $h$ be two primitive roots modulo $p$. Show that $gh$ is not a primitive root modulo $p$.

I think I'll need to use the fact that if $g$ is a primitive root modulo p then a reduced residue system modulo $p$ is $g$, $g^2$,..., $g^{p-1}$

Any help would be much appreciated!

  • $\begingroup$ Hint: since $h$ is non-zero mod $p$ it must be equal to $g^k$ for some positive integer $k$ (since $g$ is a primitive root). Now try to deduce something about $k$ knowing that $h$ is a primitive root and $p$ is odd. Can $g^{k+1}$ also be a primitive root? $\endgroup$ – Erick Wong Mar 5 '18 at 16:17


$$g^{(p-1)/2}\equiv h^{(p-1)/2}\equiv-1\pmod p$$


  • $\begingroup$ See math.stackexchange.com/questions/502089/… $\endgroup$ – lab bhattacharjee Mar 5 '18 at 16:12
  • $\begingroup$ So (gh)$^{(p-1)/2}$ $\equiv$ 1 (mod p) , but how does that prove that gh is not a primitive root of mod p? I'm sorry, I've looked through the answers to the question you sent, which was very helpful, but I'm still having trouble connecting everything. $\endgroup$ – vfantina Mar 5 '18 at 16:33
  • $\begingroup$ @vfantina, So, ord$_p(gh)\le\dfrac{p-1}2<p-1$ $\endgroup$ – lab bhattacharjee Mar 5 '18 at 16:39

ANSWER AND COMMENT.-It is known that if $g$ is a primitive root modulo $p$ the other possible primitive roots are given by $g^n=h$ where $(n, \phi(p))=(n,p-1)=1$. Therefore if $$gh=g^{n+1}$$ is another primitive root, then $$(n+1,p-1)=1$$ It is not possible to have both $$(n, p-1)=1\text{ and } (n+1,p-1)=1\space \space \text {(why?) }$$.

Example of searching another primitive root.

$3$ is a primitive root modulo $7$ and $\phi(7)=6$. Thus $3^5=5$ modulo $7$ is the only other p.r. because $2,3,4,6$ are not coprime with $6$ (exponent $1$ corresponds to the p. r. $3$ itself). There are just two primitive roots modulo $7$.


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.