let $q$ be a prime of the form $q=3r+1$ and assume that $p=4q+1$ is also a prime. Show that $3$ is a primitive root of $p$

Question

How to even begin? The proof for if $p$ is an odd prime then $(\frac{2}{p})=(-1)^{\frac{p^{2}-1}{8}}$ seems useful but not sure how to adapt it

Answer 1

By Fermat's Theorem, we have $3^{4q}\equiv 1\pmod{p}$. So the order of $3$ divides $4q$. We show that $3$ is a primitive root of $p$ by showing that the order of $3$ modulo $p$ is exactly $4q$. This can be done by showing that $3$ does not have order $1$, $2$, $4$, $q$, or $2q$.

Note that $3$ is a quadratic non-residue of $p$. For let us calculate the Legendre symbol $(3/p)$. By quadratic reciprocity, since $p$ has shape $4k+1$, we have $(3/p)=(p/3)$. We have $p=12r+5$, and therefore $(p/3)=(5/3)=(2/3)=-1$.

It follows that $3^{2q}\equiv -1\pmod{p}$. This implies that $3$ does not have order $2q$ or $q$.

We leave it to you to show that $3$ does not have order $1$, $2$, or $4$ modulo $p$.