Existence of solution to the equation $x^2+2y^2=p$ or $2p$ Prove that given a prime $p$ at least one of the following equations have a solution:
$x^2+2y^2=p$, $x^2+2y^2=2p$.
The hint is “consider the pairs $(u, v)$ in $u+av$ where $a$ satisfies $p|a^2+2$.
Since the textbook has not reach the ring extension of $\mathbb{Z}$ nor any other theorems except for the Wilson’s theorem and Euler’s theorem, please try to use elementary method if possible.
The problem is in section $2.1$ #$56$, in the book An Introduction to the Theory of Numbers by Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery.
I tried to prove the existence of solution nonconstructive, just as we prove that there are irrational pairs $(a,b)$ such that $a^b$ is rational. I also tried to follow the hint but I failed to understand what the hint really says.
 A: The claim is false. There is no solution for either equation for $p=5$.
In fact, $x^2+2y^2=p$ has a solution iff $x^2+2y^2=2p$ has a solution:


*

*If $x^2+2y^2=p$, then $(2y)^2+2x^2=2p$.

*If $x^2+2y^2=2p$, then $x=2z$ and $y^2+2z^2=p$.
Finally, $x^2+2y^2=p$ has a solution iff $p \equiv 1,2,3 \bmod 8$. See OEIS/A033203.
A: COMMENT.-$$x^2+2y^2=p\Rightarrow (y,p)=1\Rightarrow yw=1\text { for some }w\in\mathbb F_p$$
It follows $$y^2w^2x^2+2y^2=y^2(w^2x^2+2)=0\Rightarrow -2\text{ is quadratic residu modulo p }$$
Hence a necessary condition for the equation $x^2+2y^2=p$ have solution is that $-2$ be a quadratic residu modulo $p$. It is known that there are infinitely many of these primes.
I can not to prove that this is also sufficient condition.
On the other hand $x^2+2y^2=2p$ become the first equation multiplying by $2$ and again $-2$ quadratic residu modulo $p$ is a necessary condition in order there is solution.
A: I guess that the intended solution was related to the Thue's lemma (see here, for example https://en.wikipedia.org/wiki/Thue%27s_lemma).
We need this statement in the following form:
Lemma. Let $p$ be a prime and $a\in\mathbb{F}_{p}^{\times}$ (i.e. nonzero residue modulo $p$). Then, there are nonzero integers $x$ and $y$ such that $|x|,|y|<\sqrt{p}$ and $x+ay\equiv 0\pmod p$.
Proof (sketch). As was hinted in the book, consider all pairs $(u,v)$, where $u,v\in\{0,1,\ldots,[\sqrt{p}]\}$, and let $g(u,v)=u+av\pmod p$. Since $([\sqrt{p}]+1)^2>p$, there are two pairs $(u_1,v_1)$ and $(u_2,v_2)$ such that $g(u_1,v_1)\equiv g(u_2,v_2)\pmod p$. Finally, put $x=u_1-u_2$ and $y=v_1-v_2$
Now, as @Piquito pointed out, due to the necessary condition for the existence of solutions, $-2$ should be a quadratic residue modulo $p$.
Then, apply lemma for $a\in a\in\mathbb{F}_{p}^{\times}$ such that $a^2\equiv -2\pmod p$. It clear that in this case for nonzero integers $x$ and $y$ we have $x^2+2y^2\equiv x^2-a^2y^2\equiv 0\pmod p$. On the other hand, $0<x^2+2y^2<p+2p=3p$ and, thus, $x^2+2y^2\in\{p,2p\}$, as desired.
