Show that $-3$ is a primitive root modulo $p=2q+1$

Question

This was a question from an exam:

Let $q \ge 5$ be a prime number and assume that $p=2q+1$ is also prime. Prove that $-3$ is a primitive root in $\mathbb{Z}_p$.

I guess the solution goes something like this:

Let $k$ be the order multiplicative order of $-3$ modulo p. Using Euler's theorem we see that: $(-3)^{2q} \equiv1\ (mod\ p)$. Hence $k\ |\ 2q$, which means (since $q$ is prime) that $k=1,\ 2,\ q,$ or $2q$. Obviously $k \neq 1$ and $k \neq 2$, since otherwise we'll have $[-3]_p=[1]_p$ and $[(-3)^2]_p = [9]_p = [1]_p$, respectively, which is wrong since $ p \ge 11$. What remains is to show that $k \neq q$. Unfortunately, I could not figure out how to show this.

Answer 1

Hint:

If $(-3)^q\equiv1\pmod p$, then $(-3)^{\frac{p-1}2}\equiv1\pmod p$, hence $-3$ would be a quadratic residue modulo $p$.

You could write this as

$$\left(\!\frac{-3}{p}\!\right)=1$$ and play around with the Law of Quadratic Reciprocity and other properties of the Legendre symbol.

This will allow you to conclude something very interesting.

---

Edit:

I'll show how I personally would handle with the Legendre symbols.

We have $$\begin{align}1=\left(\!\frac{-3}{p}\!\right)&=\left(\!\frac{-1}{p}\!\right)\cdot\left(\!\frac{3}{p}\!\right)\\&=(-1)^{\frac{p-1}2}\cdot\left(\!\frac{3}{p}\!\right)\\ &=(-1)^q\cdot(-1)^{\frac{(p-1)(3-1)}{4}}\cdot\left(\!\frac{p}{3}\!\right)\\ &=(-1)\cdot(-1)\cdot\left(\!\frac{p}{3}\!\right)\end{align},$$ hence $\left(\!\frac{p}{3}\!\right)=1$, which means $p\equiv1\pmod3$. This would imply $3\mid p-1=2q$, a contradiction.

Answer 2

Hint: If $(-3)^q \equiv 1 (mod p)$ then $-3$ is a quadratic residue modulo $p$ (because if $\xi$ is a primitive root and $(\xi^k)^q \equiv 1$ then $k$ is even and $\xi^k$ is a quadratic resieue)