I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field.
Consider the equation:
$$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$
For which primes $p$ is it possible for this equation to have solutions in $a$ and $b$?
I wrote a quick brute force number crunching program to find that for primes 3, 5, 11, 13, and 19 there are no solutions in $a$ and $b$.
However, for primes 7 and 17, there exist solutions.
Is there a discernible condition on $p$ such that this congruence has solutions?
Yes—indeed this is a classical motivating problem of number theory, addressed by Euler and Gauss among others.
First of all, note that $a\equiv b\equiv0\pmod p$ is a solution for any $p$; I assume you mean to exclude these trivial solutions. That means we can assume that neither $a$ nor $b$ is $0\pmod p$ (since if one is, the other is too).
In particular, $b$ is invertible modulo $p$, and so the congruence is equivalent to $(ab^{-1})^2 \equiv 2\pmod p$. Therefore if the congruence has nontrivial solutions, so does the congruence $x^2\equiv2\pmod p$. Conversely, if $x^2\equiv2\pmod p$ has solutions, then take $a=x$ and $b=1$.
So we've reduced the problem to deciding which primes $p$ have "square roots of $2$"; in other words, we want to know for which primes $2$ is a quadratic residue. And this is a classical theorem: they are exactly the primes congruent to either $1$ or $7$ modulo $8$.