Thread: Proving 3 is primitive root modulo p

I think I've found a proof for the following but would really appreciate if someone could either point out where I've gone wrong (there are a couple of steps which I'm not 100% happy with) or perhaps suggest a more simple approach. Anyway, here is the problem:

Let p be prime. Let p == 2 mod 3 and p-1 = 4q (for some prime q)>

1) a) Prove

My proof:



which contradictions our assumption that

Could anyone tell me if this proof is correct? Thanks!

Originally Posted by Ant

I think I've found a proof for the following but would really appreciate if someone could either point out where I've gone wrong (there are a couple of steps which I'm not 100% happy with) or perhaps suggest a more simple approach. Anyway, here is the problem:

Let p be prime. Let p == 2 mod 3 and p-1 = 4q (for some prime q)>

1) a) Prove

My proof:



which contradictions our assumption that

Could anyone tell me if this proof is correct? Thanks!

Actually :



so you have two cases..

Originally Posted by princeps

Actually :



so you have two cases..

oh yes, of course. I think I was too hung up on trying to prove that the order of 3 wasn't 4 that I forgot that case.

Either way, is working above, where I divide LHS and RHS by 3 okay? Because I'm not sure I know for certain that (p-1)/3 is an integer?

Originally Posted by Ant

oh yes, of course. I think I was too hung up on trying to prove that the order of 3 wasn't 4 that I forgot that case.

Either way, is working above, where I divide LHS and RHS by 3 okay? Because I'm not sure I know for certain that (p-1)/3 is an integer?

Hence :



but, primes and cannot be expressed in form for some prime therefore we have contradiction .

Q.E.D.

Ah I see it. Thanks!

For some reason I was reluctant to write 3^2 as 9, as soon as you do that it becomes obvious.

For the case where

A similar argument proves that p divides 8 which implies that p=2. Which contradicts p-1=4q (some prime q).