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.
Solutions to $x^2+x-1\equiv 0$ mod $p$
elementary-number-theoryquadratic-reciprocity
Best Answer
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.)