Results 1 to 2 of 2

Math Help - Primitive Root proof

  1. #1
    Newbie
    Joined
    Feb 2010
    From
    Santa Monica, California
    Posts
    7

    Primitive Root proof

    Let p = 2^(k) + 1 be a prime. Prove that if a is a natural number and a is a quadratic non-residue modulo p, then a is a primitive root modulo p.

    thanks
    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 Tand View Post
    Let p = 2^(k) + 1 be a prime. Prove that if a is a natural number and a is a quadratic non-residue modulo p, then a is a primitive root modulo p.

    thanks
    Euler's Criterion says  -1 = \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \bmod{p}

    But  \frac{p-1}{2} = 2^{k-1} , so we know  a^{2^{k-1}}\equiv -1 \bmod{p} .

    Now all the divisors of  \phi(p) are of the form  2^b where  b\leq k . So suppose there exists  b < k-1 such that  a^{2^b}\equiv 1\bmod{p} . This would however imply  a^{2^{k-1}}\equiv 1 \bmod{p} since  2^b\mid2^{k-1} , which is a contradiction.

    Thus we see for every proper divisor  b of  \phi(p) ,  a^b\not\equiv 1 \bmod{p}\implies a is a primitive root modulo  p .
    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 of 2^n + 1
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 9th 2010, 12:34 PM
  3. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 08:49 AM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2009, 05:53 PM
  5. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 07:47 PM

Search Tags


/mathhelpforum @mathhelpforum