Results 1 to 2 of 2

Math Help - Prove that 2 is a primitive root modulo p.

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    34

    Prove that 2 is a primitive root modulo p.

    Suppose q is a prime and p=4q+1 is a prime. Prove that 2 is a primitive root modulo p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by NikoBellic View Post
    Suppose q is a prime and p=4q+1 is a prime. Prove that 2 is a primitive root modulo p.
    First observe that  2^{\frac{p-1}{2}}\equiv\pm 1 \mod{p} .

    In this case,  2 is a primitive root if and only if  2^{\frac{p-1}{2}}\equiv -1 \mod{p} . (Ask if you'd like to see the proof of this.)

    Assume otherwise, so  2^{\frac{p-1}{2}}\equiv 1 \mod{p} .
    Note  \frac{p-1}{2} = 2q .

    Now by Euler's Criterion,  2^{2q}\equiv 1\mod{p} \iff \left(\frac{2}{p}\right)=1

     \left(\frac{2}{p}\right)=1 \implies p\equiv 1 \text{ or } 7\mod{8} . Since  p\equiv 1 \mod{4} \implies p\equiv 1 \text{ or } 5 \mod{8} . Thus  p\equiv 1\mod{8} \implies 8\mid p-1 \implies 8\mid 4q \implies 2\mid q \implies q=2 , which is a contradiction since  4\cdot 2+1 =9 is not prime.

    Thus  2^{\frac{p-1}{2}} \not\equiv 1 \mod{p} \implies 2^{\frac{p-1}{2}}\equiv -1 \mod{p} \implies 2 is a primitive root modulo  p .
    Last edited by chiph588@; March 27th 2010 at 11:01 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. p=2^k+1 and (a/p)=-1 imply a is primitive modulo p
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2010, 07:34 AM
  3. primitive root modulo p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 23rd 2010, 02:42 AM
  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