Let $p$ be an odd prime number and $g$ and $g^\prime$ be primitive elements in $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$.
Proof that $gg^\prime$ is not a primitive element in $\mathbb{F}_p$.

Maybe it's possible to proof by contradiction, starting from the basis that $gg^\prime$ ist a primitive elements in $\mathbb{F}_p$, then $\gcd(gg^\prime, \big|\mathbb{F}_p\big|) = 1 \implies {(gg^\prime)}^{p-1} \equiv 1\, (\text{ mod } p)$.
But I can not find a concrete solution.

  • 3
    $\begingroup$ Every primitive root is a quadratic non-residue. $\endgroup$ Oct 25, 2017 at 20:51

1 Answer 1


Let $g'=g^k$ for some $k$. Since $\mathrm{ord}_p(g')=p-1$, we have that $\gcd(k,p-1)=1$. Specifically, $k$ is odd (as $p-1$ is even). Thus $k+1$ is even, so $gg'$ is a quadratic residue, thus nonprimitive.


You must log in to answer this question.

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