Quadratic Residues

**cathwelch** · May 11th 2009, 07:35 PM

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.

**fardeen_gen** · May 12th 2009, 09:42 AM

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.

Thread: Quadratic Residues

LinkBack

Thread Tools

Display