The idea in NonCommAlg's post was to look at the equation , where for some integer . Multiplying both sides by 4 gives . Subtracting 3 from both sides gives . We factor the left hand side: .
My original idea was somewhat similar. I first looked at the quadratic equation: . This can be interpreted as a formula modulo by making a few modifications. We should take to mean and to mean the square root modulo . (If you are not comfortable with this, try actually completing the square and solving for , all modulo .) Then, it follows that a quadratic polynomial modulo has roots if and only if the discriminant is a quadratic residue. In the case of the problem, (it is not a coincidence that this is the same as in the above), and we can apply the reciprocity argument as NonCommAlg outlined already.