Solution to $x^2+x-1\equiv 0$ mod $p$ I need help in understanding the solutions to 
$x^2+x-1\equiv 0 \mod p.$
I have run some tests and found that for there are no solutions for p=13,17,23,37,43,47 and there are exactly 2 solutions for p=11,19,29,31,41.
I guess the first step would be showing which primes do/do not have a solution and showing that those that do only have 2 solutions, and if possible finding the solutions.
Thanks. Any help will be appreciated.
 A: First understand that $4$ is invertible $\mod p,$ so we have $x^2+x-1 = 0 \mod p $ if and only if $4x^2+4x-4=0 \mod p.$ The idea is to complete the square, we can write the previous equation as $(2x+1)^2 = 5 \mod p.$ So now you can solve that equation whenever you can solve $y^2 = 5 \mod p.$ Putting the problem in this form should remind you of quadratic reciprocity.
A: The solutions are given by the usual formula: $x_{1,2}=\frac{-1\pm\sqrt{5}}{2}$. The problem is just to make sense of the operations involved. Division by $2$ is possible only if $p\ne 2$ (and we explicitly check that there is no solution $\pmod 2$). And a square root of $5$ exists only modulo certanin $p$ (for example $4^2=16\equiv 5\pmod{11}$). The law of quadratic reciprocity tells us that $5$ is a square $\pmod p$ iff $p$ is a square $\pmod 5$, that is iff $p\equiv \pm1\pmod 5$ or $p=5$. So for these $p$ there are  solutions (a single solution for $p=5$ where $\sqrt 5=0$, two distinct solutions otherwise), whereas for $p\equiv \pm2$ there is no solution.
