# Proving 3 is primitive root modulo p

• Apr 3rd 2012, 03:30 AM
Ant
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 $3^4 \not\equiv 1 \, \, \: (mod p)$

My proof:

$3^4 \equiv 1 \, (mod p) \,\:\:\Leftrightarrow\:\:3^2 \equiv -1\,(mod p)\Leftrightarrow\:\:3^2\equiv\(p-1)\,(mod p) \:\:\Leftrightarrow\:\:3\equiv \frac{p-1}{3}\,(mod\, p)\:\:\Leftrightarrow\:\: 3+kp \equiv \frac{p-1}{3} \:\:\Leftrightarrow\:\: 9 +3kp = p-1\:\:\Leftrightarrow\:\:\(p-1)\equiv0\,(mod3)\:\:\Leftrightarrow\:\:\ p\equiv1(mod3)$

which contradictions our assumption that $p\equiv 2\,(modp)$

Could anyone tell me if this proof is correct? Thanks!
• Apr 3rd 2012, 04:33 AM
princeps
Re: Proving 3 is primitive root modulo p
Quote:

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 $3^4 \not\equiv 1 \, \, \: (mod p)$

My proof:

$3^4 \equiv 1 \, (mod p) \,\:\:\Leftrightarrow\:\:3^2 \equiv -1\,(mod p)\Leftrightarrow\:\:3^2\equiv\(p-1)\,(mod p) \:\:\Leftrightarrow\:\:3\equiv \frac{p-1}{3}\,(mod\, p)\:\:\Leftrightarrow\:\: 3+kp \equiv \frac{p-1}{3} \:\:\Leftrightarrow\:\: 9 +3kp = p-1\:\:\Leftrightarrow\:\:\(p-1)\equiv0\,(mod3)\:\:\Leftrightarrow\:\:\ p\equiv1(mod3)$

which contradictions our assumption that $p\equiv 2\,(modp)$

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

Actually :

$3^4 \equiv 1 \pmod p \Leftrightarrow 3^2 \equiv -1 \pmod p ~\text{ or }~3^2 \equiv 1 \pmod p$

so you have two cases..
• Apr 3rd 2012, 07:04 AM
Ant
Re: Proving 3 is primitive root modulo p
Quote:

Originally Posted by princeps
Actually :

$3^4 \equiv 1 \pmod p \Leftrightarrow 3^2 \equiv -1 \pmod p ~\text{ or }~3^2 \equiv 1 \pmod p$

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?
• Apr 3rd 2012, 07:33 AM
princeps
Re: Proving 3 is primitive root modulo p
Quote:

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?

$3^2 \equiv -1 \pmod p \Leftrightarrow 3^2+1 \equiv 0 \pmod p \Leftrightarrow 10 \equiv 0 \pmod p$

Hence :

$p \in \{2,5\}$

but, primes $2$ and $5$ cannot be expressed in form $p=4q+1$ for some prime $q$ therefore we have contradiction .

Q.E.D.
• Apr 3rd 2012, 09:09 AM
Ant
Re: Proving 3 is primitive root modulo p
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 $3^2\equiv1 (modp)$

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