I commonly run into the following question such that if $p$ and $q=4p+1$ are both odd primes prove that $2$ is primitve root modulo q . However , i could not prove it for other number that are given at the end , so can you help me for them , how should we approach them when they are negative , i could not deduce the solution

What i obtained: The part for $2$ , i have the following :

Note that $q\not=2$ since $4\cdot2+1=9$ is not prime. $\mathrm{ord}_p(2)\vert p-1=4q$, so $\mathrm{ord}_p(2)=1,\;2,\;4,\;q,\;2q,\;\mathrm{or}\;4q$.

Clearly $\mathrm{ord}_p(2) \not= 1$, and $\mathrm{ord}_p(2)\not=2$ since $4\equiv1(\text{mod }p) \implies p=3$ but $3\not=4q+1$ for any positive integer $q$. Also $\mathrm{ord}_p(2)\not=2$ because $2^4=16\equiv1(\text{mod }p)\implies p=3 \text{ or } 5$. It has been shown that $p\not=3$ and $p=5\implies q=1$ which is not prime.

Suppose $\mathrm{ord}_p(2)=q$. Then $2^q\equiv1(\text{mod }p)$. Let $g$ be a primitive root modulo $p$, so that $2\equiv g^i(\text{mod }p)$ for some $i\in\mathbb{Z}$. Then $$g^{iq}\equiv1(\text{mod }p)\implies p-1\vert iq\implies iq=k(p-1)=4kq\implies i=4k$$ for some $k\in\mathbb{Z}$. So $2\equiv g^{4k}(\text{mod }p)$ and $2$ is a square modulo $p$, which means $p\equiv\pm1(\text{mod }8)$. Hence, either $8\vert p-1$ or $8\vert p+1$. If $8\vert p-1$, then $p-1=4q=8l\implies q=2l$ for some $l\in\mathbb{Z}$, so $q$ is even, which is impossible since $q\not=2$. If instead $8\vert p+1$, then $p+1=4q+2=8l\implies2q+1=2l$ for some $l\in\mathbb{Z}$, which is impossible. Thus $\mathrm{ord}_p(2)\not=q$.

Suppose $\mathrm{ord}_p(2)=2q$. Then $2^{2q}\equiv1(\text{mod }p)$. Let $g$ be a primitive root modulo $p$, so that $2\equiv g^i(\text{mod }p)$ for some $i\in\mathbb{Z}$. Thus $$g^{2iq}\equiv1(\text{mod }p)\implies p-1\vert 2iq\implies2iq=4kq\implies i=2k$$ for some $k\in\mathbb{Z}$, so $2$ is a square modulo $p$, which has been shown to be false. Therefore $\mathrm{ord}_p(2)\not=2q$.

Hence $\mathrm{ord}_p(2)=4q=p-1$ and 2 is a primitive root modulo $p$.

However , i stuck in showing that $-2$ is also primitive roots modulo $q$. Moreover , how can we show that $3$ and $-3$ are also primitve roots if $p >3$

  • $\begingroup$ What is meant with "nice solution" in context with a primitive root ? $\endgroup$
    – Peter
    Nov 20, 2022 at 20:25
  • $\begingroup$ Your argument is similar to this one, so I guess I endorse it :-). $\endgroup$ Nov 20, 2022 at 20:37
  • $\begingroup$ Hint: $q\equiv1\pmod4$, so we know that $-1$ is a quadratic residue modulo $q$. Would that help with $-2$? $\endgroup$ Nov 20, 2022 at 20:39
  • $\begingroup$ @JyrkiLahtonen but what happen for negatives and if $p >3$ for $3,-3$. $\endgroup$
    – user1121946
    Nov 20, 2022 at 20:39
  • $\begingroup$ Thinking... Are you familiar with the rest of the law of quadratic reciprocity? What do you know about the residue class of $q$ modulo $3$? $\endgroup$ Nov 20, 2022 at 20:42


You must log in to answer this question.