Quadratic congruence with linear term

Question

I'm trying to determine whether the congruence $x^2+x-1\equiv0\pmod{61}$ has a solution.

I know how to do this without the linear term, for instance, $x^2-5\equiv0\pmod{61}$.

I can solve it just by using the properties of the Legendre symbol.

But what do I do if there's a linear term?

Answer 1

We complete the square!

$$x^2+x-1 \equiv 0 \pmod{61} \iff 4x^2+4x-4 \equiv 0 \pmod{61} \iff (2x+1)^2 \equiv 5 \pmod{61}$$

Therefore, it suffices to find $$\left( \frac{5}{61} \right)$$ which can be done easily by the law of quadratic reciprocity.