Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$. Would appreciate some proof-checking here.

First, we show that a primitive root is always a quadratic non-residue. We have $x$ as a quadratic residue if $x$ satisfies $x^2 \equiv a\ mod\ p$. Note the order of $x$ divides $\phi(p)/2$. But if $x$ is a primitive root, order is $\phi(p)$ so any quadratic residue is not a primitive root.

Now, $(\frac{a}{p}) = -1$ and $(\frac{b}{p}) = -1$, so $(\frac{ab}{p}) = 1$, therefore $ab$ is a quadratic residue and as such not a primitive root $mod\ p$.

  • 1
    $\begingroup$ Imo, very good and correct. +1 $\endgroup$ – DonAntonio Apr 7 '18 at 19:42

Your Answer

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

Browse other questions tagged or ask your own question.