Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$p,q$ are primes we are given $p = 1 \pmod{3}$ and $q=4p+1$ and are asked to find $\text{order}_q(3)$, i.e to show that it is a primitive root of $\mod q$

what I have so far: using the Quadratic reciprocity: $3^{(q-1)/2}=-1\pmod{q}$ and I'm stuck :/

share|cite|improve this question
Are $p$ and $q$ prime? – Calvin Lin Feb 2 '13 at 18:14
oh yeah XD spaced out – Rachel Bernoulli Feb 2 '13 at 18:15

We need $p,q$ to be prime.

As $q-1=4p, 3^{2p}\equiv-1\pmod q\implies 3^{4p}\equiv1\pmod q,$ this also comes directly from the Fermat's Little Theorem.

So, $ord_q3\mid (4p)$ but $ord_q3\not\mid (2p)$

But the divisors of $4p$ are $1,2,4,p,2p,4p\implies ord_q3$ can only be $4p=q-1$ hence $3$ is a primitive root of $q$

share|cite|improve this answer
The first statement is 'bad' because the conclusion is obvious by Euler's theorem, but the initial condition is not (i.e. using quadratic reciprocity) – Calvin Lin Feb 2 '13 at 18:18
@CalvinLin, I'm not sure what is obvious. How about the current version? – lab bhattacharjee Feb 2 '13 at 18:22
Yeah it's good I got it thanks, thank you all :] – Rachel Bernoulli Feb 2 '13 at 18:23
@AddarBokobza, my pleasure. Why don't you include that $p,q$ are primes in the question itself? – lab bhattacharjee Feb 2 '13 at 18:25
@labbhattacharjee I meant that $3^{4p} \equiv 1 \pmod {4p+1}$ follows from FLT / Euler, and is considered much more basic than $3^{2p} \equiv -1 \pmod{q}$ which requires Quadratic reciprocity. It's a personal preference to not have result using higher power tools to imply a well know result. – Calvin Lin Feb 2 '13 at 18:33

You are very close. You haven't used the fact that $p$ is prime yet.

Hint: What are the possible orders of any element modulo $q$?

Hint: Since you showed that $3^{(q-1)/2} = -1 \pmod{q}$, what does that imply the order of 3 CANNOT be?

share|cite|improve this answer

By Fermat's Theorem, we have $3^{4p}\equiv 1\pmod{q}$.

So the order of $3$ divides $4p$.

But since $4p$ has very few divisors, all we need to do is to rule out orders $1$, $2$, $4$, $p$, and $2p$.

Your calculation will be very useful for that!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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