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.


(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.

  • $\begingroup$ $3^4\equiv 1\pmod p\iff p|80$ $\endgroup$ May 14, 2015 at 22:56

1 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.

  • $\begingroup$ Is that a typo in your first line? Shouldn't it say $3$ modulo $p$? $\endgroup$
    – George1811
    May 14, 2015 at 22:59
  • $\begingroup$ Yes, thank you! Definitely $p$. $\endgroup$ May 14, 2015 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.