Because is a quadratic residue let so and since is a quadratic residue we know ; let and we are done.
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.