Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By princeps
  • 1 Post By princeps

Math Help - Proving 3 is primitive root modulo p

  1. #1
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    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!
    Last edited by Ant; April 3rd 2012 at 02:40 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    Re: Proving 3 is primitive root modulo p

    Quote Originally Posted by Ant View Post
    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..
    Thanks from Ant
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    Re: Proving 3 is primitive root modulo p

    Quote Originally Posted by princeps View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    Re: Proving 3 is primitive root modulo p

    Quote Originally Posted by Ant View Post
    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.
    Thanks from Ant
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    137
    Thanks
    4

    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).
    Last edited by Ant; April 3rd 2012 at 08:34 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  2. primitive root modulo p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 23rd 2010, 02:42 AM
  3. Prove that 2 is a primitive root modulo p.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 21st 2010, 05:51 PM
  4. powers modulo p and primitive root question
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 16th 2008, 10:57 AM
  5. Primitive root modulo 121
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 8th 2008, 07:09 AM

Search Tags


/mathhelpforum @mathhelpforum