Because is a quadratic residue let so and since is a quadratic residue we know ; let and we are done.

EDIT:

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

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

Let be a solution to the congruence.

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

In particular, then, is a solution to our original equation.