Results 1 to 3 of 3

Math Help - primitive root modulo p

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    36

    primitive root modulo p

    Suppose p, q are primes with p = 2q + 1.

    Under what conditions on q is 5 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 vinnie100 View Post
    Suppose p, q are primes with p = 2q + 1.

    Under what conditions on q is 5 a primitive root modulo p?
    First observe  5^{\frac{p-1}{2}}\equiv\pm1\mod{p} .

    In this case,  5 is a primitive root modulo  p \iff 5^{\frac{p-1}{2}}\equiv -1 \mod{p} (Ask if you'd like to see why.)

    Note  \frac{p-1}{2} = q

    By Euler's Criterion,  5^q\equiv -1\mod{p}\iff\left(\frac{5}{p}\right)=-1 \iff p\equiv 2 \text{ or } 3\mod{5}

     p=5k+2=2q+1\iff 2q=5k+1\iff 2q\equiv1\mod{5}\iff q\equiv 3 \mod{5}
     p=5k+3=2q+1\iff 2q=5k+2\iff 2q\equiv2\mod{5}\iff q\equiv 1 \mod{5}

    So  5 is a primitive root modulo  p \iff q\equiv 1\text{ or }3 \mod{5} .
    Last edited by chiph588@; March 27th 2010 at 11:01 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Thanks very much! It makes perfect sense. I could not progress before since I could not see the trick of using Euler's criterion.

    Thanks again!
    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. 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