1
$\begingroup$

show that if $g$ and $g'$ are primitive roots modulo an odd prime $p$, then $gg'$ is not primitive root of $p$. I know that $g^\phi\equiv 1 \pmod {p}$ .Similarly for $g'$ , but what can I do further.

$\endgroup$
1
  • 1
    $\begingroup$ here $\phi$ replaces with $\phi(p)$ $\endgroup$ Oct 5, 2015 at 7:35

2 Answers 2

1
$\begingroup$

Let $g^{\phi(p)/2}= a$, by Fermat's Little Theorem, $p|(a^2-1)=(a-1)(a+1)$

As ord$_pg=\phi(p),p\nmid(a-1)\implies g^{\phi(p)/2}\equiv-1\pmod p$

$$\implies (gg')^{\phi(p-1)/2}\equiv?$$

$\implies$ord$_p(gg)'\le\dfrac{\phi(p)}2<\phi(p)$

$\endgroup$
1
$\begingroup$

As $g$ is a primitive root, we can write $g'=g^i$ for some $i$ with $(i,p-1)=1$. In particular, $i$ must be odd (as $(2j,p-1)≥2$). But then $i+1$ is even so $gg'=g^{i+1}$ is not a primitive root.

$\endgroup$

You must log in to answer this question.

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