Results 1 to 2 of 2

Math Help - Primitive Roots and Quadratic Residues

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Primitive Roots and Quadratic Residues

    I'm struggling with the concept of primitive roots and their application in certain proofs. I'm struggling with starting this problem:
    Let a and n be in the natural numbers and let p be an odd prime where p does not divide a. Using primitive roots show  x^2 \equiv a mod p is solvable if and only if y^2 \equiv a mod p^n is solvable.
    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    The idea is that \alpha,...,\alpha^{p-1} are a complete set of residues mod p when \alpha is a primitive root.

    So you can write a\equiv\alpha^k for some integer k, given any nonzero a.

    You might want to show that a^{(p-1)/2}\equiv \pm 1, the 1 and the -1 holding respectively if a is a square or not.
    To do this, assume a is a power of some primitive root and see where you can take it from there.
    Last edited by Bruno J.; June 17th 2009 at 03:04 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. quadratic nonresidue proof with primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 14th 2009, 01:35 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 04:13 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 07:15 PM

Search Tags


/mathhelpforum @mathhelpforum