Results 1 to 2 of 2

Math Help - quadratic nonresidue proof with primitive roots

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    14

    quadratic nonresidue proof with primitive roots

    Let p be an odd prime. Prove that every primitive root of p is a quadratic nonresidue. Prove that every quadratic nonresidue is a primitive root if and only if p is of the form 2^{2^n} + 1 where n is a non-negative integer, that is, if and only if p=3 \mbox{ or } p is a Fermat number.

    I have no clue what to do.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Assume a primitive root  g modulo  p is a QR. Then there exists an  x such that  x^2 \equiv g \mod{p} . But then  g^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \mod{p} . Hence we just showed  g has an order less than  \phi(p)=p-1 . Therefore we've reached a contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Quadratic nonresidue sum
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 11th 2010, 02:37 PM
  2. primitive roots proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 4th 2009, 04:25 AM
  3. Primitive Roots and Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 17th 2009, 12:43 PM
  4. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 24th 2009, 12:27 PM
  5. Primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 19th 2006, 05:32 AM

Search Tags


/mathhelpforum @mathhelpforum