Results 1 to 2 of 2

Math Help - Quadratic Residues

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    25

    Quadratic Residues

    Question:
    If a and b are both quadratic residues of the odd prime p or both non-residues of p, show that the congruence ax^2 =b (modp) has a solution.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    Because a is a quadratic residue let a\equiv s^2 so ax^{2}\equiv (sx)^{2} and since b is a quadratic residue we know b\equiv t^2; let t = sx and we are done.

    EDIT:
    I had failed to consider the case where they both are non-residues.

    ax^2 = b\ \pmod{p}
    (ax)^2 = ab\ \pmod{p}

    This is solvable only when ab is a quadratic residue; by euler's criterion, ab is a quadratic residue iff and only iff both or neither of a and b are quadratic residues.

    Let ax\equiv s\pmod{p} be a solution to the congruence.

    By the Euclidean algorithm, a has a modular inverse since it is relatively prime to p (if p|a, then there would be no such s . If a\equiv 0,do we consider it a quadratic residue or what?).

    In particular, then, x\equiv a^{-1}s\pmod{p} is a solution to our original equation.
    Last edited by fardeen_gen; May 13th 2009 at 09:39 AM. Reason: Failed to consider a case
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 11th 2011, 11:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 12:25 PM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 09:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 03:19 PM
  5. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 07:45 PM

Search Tags


/mathhelpforum @mathhelpforum