# Finding primitive roots including negative sign

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

• What is meant with "nice solution" in context with a primitive root ? Nov 20, 2022 at 20:25
• Your argument is similar to this one, so I guess I endorse it :-). Nov 20, 2022 at 20:37
• Hint: $q\equiv1\pmod4$, so we know that $-1$ is a quadratic residue modulo $q$. Would that help with $-2$? Nov 20, 2022 at 20:39
• @JyrkiLahtonen but what happen for negatives and if $p >3$ for $3,-3$.
– user1121946
Nov 20, 2022 at 20:39
• 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$? Nov 20, 2022 at 20:42