Finding all primes $p$ for which $p\mid x^2-x-1$ for some $x\in \mathbb Z$.

Question

I would like to characterize all primes $p$ for which the polynomial $x^2-x-1$ has roots in $\mathbb Z_p$

If this is not possible I would like to find a family of primes for which it has roots or a family of primes for which it does not have roots. (preferably a family for which there is a rapid test to determine pertinence to the family).

Answer 1

Let $p$ be odd. Then your condition is equivalent to asking for the odd primes $p$ for which $4x^2-4x-4\equiv 0\pmod{p}$ has a solution, or equivalently for the odd primes $p$ for which $(2x-1)^2-5\equiv 0\pmod{p}$ has a solution, or equivalently for the odd primes $p$ for which $w^2\equiv 5\pmod{p}$ has a solution.

Deal separately with the prime $5$. For odd $p\ne 5$, we are asking for the $p$ such that the Legendre symbol $(5/p)$ is equal to $1$.

By Quadratic Reciprocity, we want the odd $p\ne 5$ such that $(p/5)=1$. These are the odd primes of the form $5k+1$ or $5k-1$.

It remains to deal with $p=2$ and $p=5$.

Answer 2

It is never divisible by $2$.

Now we complete the square.

When $p$ is odd, $$\begin{align}x^2-x-1&\equiv x^2-(p+1)x-1\pmod{p}\\ &=\left(x-\frac{p+1}{2}\right)^2 -\left(1+\left(\frac{p+1}{2}\right)^2\right)\end{align}$$

So we need $\frac{p^2+2p+5}{4}$ a square modulo $p$, which is equivalent to when $5$ is a square modulo $p$.