1
$\begingroup$

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!

$\endgroup$
1
  • $\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, 2018 at 16:17

2 Answers 2

5
$\begingroup$

Hint:

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

$$(gh)^{(p-1)/2}\equiv?$$

$\endgroup$
3
  • $\begingroup$ See math.stackexchange.com/questions/502089/… $\endgroup$ Mar 5, 2018 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, 2018 at 16:33
  • $\begingroup$ @vfantina, So, ord$_p(gh)\le\dfrac{p-1}2<p-1$ $\endgroup$ Mar 5, 2018 at 16:39
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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