Solutions to $x^2+x-1\equiv 0$ mod $p$

Question

The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that: $$ x(x+1)\equiv 1 \pmod{p} $$ The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.

Answer 1

Completing the square is the most obvious approach. Starting from

$$x^2+x-1\equiv 0\pmod p$$

we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$: $$ 4x^2+4x-4\equiv 0\pmod p\iff (2x+1)^2\equiv 5\pmod p.$$ Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)

Answer 2

For odd $p$, multiply through by $4$ to get

$$4x^2+4x+1 \equiv 5 \pmod{p}.$$

Enough?