# $p = 1 \pmod{3}$ and $q=4p+1$ prove that $3$ is a primitive root modulo $q$

$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 :/

-
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$

-
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?

-

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!

-