Prove $3$ is a primitive root modulo $p$ given $\;p\equiv 2 \;\text{mod}\; 3\;$, $\;p-1=4q\;$, for $q$ prime.

Question

Let $p$ be a prime number which satisfies the following two conditions:

(i) $p\equiv 2 \;\text{mod}\; 3$

(ii) $p-1=4q$ where $q$ is also a prime number.

Show:

(a) that $3^4\not\equiv 1\; \text{mod}\; p$

(b) that $3^{2q}\not\equiv 1\; \text{mod}\; p$

(c) now that $3$ is a primitive root modulo $p$. [Hint: Use the results from parts (a) and (b).]

Now I haven't gotten very far with this at all. I've tried using the fact that there has to be a primitive root mod $p$ and then assumed that $3^4\equiv 1\; \text{mod}\; p$ and tried to find a contradiction but to no avail. I've found that $4|kp$ where $k\in \mathbb{Z}$. Not sure if I can infer from that, that $4|p$ which would be a contradiction. I'm not sure if there is something that I'm fundamentally missing as it seems to lead you into the question. Any hints would be appreciated.

Answer 1

Outline: We find the order of $3$ modulo $p$. This order must divide $p-1$, that is, $4q$. Note that $q$ is an odd prime. So the possible orders of $3$ modulo $p$ are $1,2,4,q,2q,4q$. We need to show the order is $4q$, so we need to eliminate the other possibilities. Together, (a) and (b) do that.

Proving (a) can be done by calculation. To prove (b), it is enough to show that $3$ is not a quadratic residue of $p$. That can be done using the given information, and Reciprocity.