Results 1 to 2 of 2

Math Help - Quadratic Residue Proof

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

    Quadratic Residue Proof

    Let p be a prime such that p is congruent to 3 modulo 4 and let a be a quadratic residue modulo p. Prove that if ab is congruent to p-1 modulo p, then b is a quadratic non-residue 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 Tand View Post
    Let p be a prime such that p is congruent to 3 modulo 4 and let a be a quadratic residue modulo p. Prove that if ab is congruent to p-1 modulo p, then b is a quadratic non-residue modulo p.
     ab\equiv p-1\equiv -1\bmod{p}\implies b\equiv-a^{-1}\bmod{p}

     \left(\frac bp\right) = \left(\frac{-a^{-1}}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{a^{-1}}{p}\right) = (-1)\cdot(1) = -1 since  p\equiv3\bmod{4} .


    You may be wondering why  \left(\frac{a^{-1}}{p}\right) = 1 .

    Well,  1=\left(\frac1p\right) = \left(\frac{a\cdot a^{-1}}{p}\right) = \left(\frac ap\right)\left(\frac{a^{-1}}{p}\right) = \left(\frac{a^{-1}}{p}\right) .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with quadratic residue
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 17th 2011, 04:17 PM
  2. [SOLVED] Quadratic Residue proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 13th 2011, 05:10 PM
  3. When is 2 a quadratic residue?
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 8th 2011, 06:49 PM
  4. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2010, 02:35 PM
  5. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 13th 2009, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum