Results 1 to 2 of 2

Thread: 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 $\displaystyle a$ is a quadratic residue let $\displaystyle a\equiv s^2$ so $\displaystyle ax^{2}\equiv (sx)^{2}$ and since $\displaystyle b$ is a quadratic residue we know $\displaystyle b\equiv t^2$; let $\displaystyle t = sx$ and we are done.

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

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

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

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

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

    In particular, then, $\displaystyle x\equiv a^{-1}s\pmod{p}$ is a solution to our original equation.
    Last edited by fardeen_gen; May 13th 2009 at 08: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: Feb 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jul 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 4th 2009, 02:19 PM
  5. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum