As $2 = x^2 -2y^2$ for $x = 2$ and $y=1$ we fix an odd prime number $p$, and

**Claim:** There exist integers $x,y$ such that $p = x^2 -2y^2$ if and only if $p \equiv \pm1 \mod 8$.

First if $p = x^2 -2y^2$ for some $x,y \in \mathbb{Z}$ then observing that the squares mod $8$ are $0,1,4$, we conclude that $p$ can only be $0,1,2,4,6,7$ mod $8$ but it is odd so $p \equiv \pm1 \mod 8$.

For the other direction, suppose that $p \equiv \pm1 \mod 8$. By a lemma of Gauss, there exists some $t \in (\mathbb{Z}/p\mathbb{Z})^*$ such that $t^2 \equiv 2 \mod p$. Define: $$S = \{a \in \mathbb{Z} \mid 0 \leq a \leq \sqrt{p}\}$$ and observe that $|S| > \sqrt{p}$. Consequently, $|S^2| > p$ so by the pigeonhole principle, there are different $(x_1,y_1),(x_2,y_2) \in S^2$ for which $x_1 - ty_1 \equiv x_2-ty_2 \mod p$, or equivalently, $x_1 - x_2 \equiv t(y_1 - y_2) \mod p$.

Set $x = |x_1 - x_2|, y = |y_1 - y_2|$ and note that $(x,y) \in S^2$ and that $x \equiv \pm t y \mod p$, so after squaring we get that $x^2 \equiv 2y^2 \mod p$, that is $p | x^2 - 2y^2$. On the other hand, $$|x^2 -2y^2| \leq |x|^2 +2|y|^2 < p + 2p = 3p.$$ Therefore, $x^2 -2y^2 \in \{-2p,-p,0,p,2p\}$.

**Case 1:** $x^2-2y^2 = 0$ which means that $x^2 = 2y^2$. Taking into account the number of times $2$ divides both sides (alternatively, set $x = 2x_0$ and apply infinite descent), we see that equality is possible if and only if $x = y = 0$, but this contradicts our assumption that $(x_1,y_1) \neq (x_2,y_2)$.

**Case 2:** $x^2 -2y^2 = 2p$. Clearly, $x$ is even. Set $a = x + y, b = x/2+y$ and observe that $a^2 -2b^2 = p$.

**Case 3:** $x^2 -2y^2 = -p$. Set $a = x + 2y, b = x + y$ and observe that $a^2 -2b^2 = p$.

**Case 4:** $x^2 -2y^2 = -2p$. Clearly, $x$ is even. Set $a = 2x + 3y, b =3x/2 + 2y$ and observe that $a^2 -2b^2 = p$.

**Case 5:** $x^2 -2y^2 = p$, which is what we want.