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

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.

• Have you tried completing the square? – JavaMan Dec 9 '18 at 23:57
• Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration. – Batominovski Dec 10 '18 at 0:03

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.)

• Oh yeah that makes sense. Thank you for the help! – joseph Dec 10 '18 at 1:51
• Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $p\equiv +/-1 \pmod{5}$ or $p=5$. – joseph Dec 10 '18 at 2:57

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

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

Enough?