For a prime $p \equiv 1$ or $3$ (mod $8$), show that the equation $x^{2} + 2y^{2} = p$ has a solution. 
For a prime $p \equiv 1$ or $3$  (mod $8$), show that the equation $x^{2} + 2y^{2} = p$ has a solution.

I'd like to see an elementary proof.
 A: Here is a particularly nice proof involving Minkowski's Convex Body theorem.
Lemma: $p\equiv 1\pmod{8}$ or $p\equiv 3\pmod{8}\iff p|a^2+2$ for some $a\in\mathbf{Z}$.
Proof: The latter statement is equivalent to $\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)=1$. It is not hard to see that this holds if and only if $p$ is of the shape $8k+1$ or $8k+3$, due to CRT. $\Box$
By our lemma, we can choose $a\in\mathbf{Z}$ such that $p|a^2+2$. Define a lattice $\mathfrak{L}\in\mathbf{R}^2$ as $\mathfrak{L}=\{m\vec{v_1}+n\vec{v_2}:m,n\in\mathbf{Z}\}$ where $\vec{v_1}=(a,1)$ and $\vec{v_2}=(p,0)$. The fundamental parallelogram $\mathfrak{F}$ of $\mathfrak{L}$ has area $p$. Let $(x,y)\in\mathfrak{L}$. Then $x=ma+p$ and $y=m$, so \begin{align*}x^2+2y^2 &= (ma+p)^2+2m^2 \\ &= m^2a^2+2map+p^2+2m^2 \\ &= m^2(a^2+2)+2map+p^2 \\ &\equiv m^2(a^2+2)\pmod{p}\\ &\equiv 0\pmod{p}\end{align*} due to our choice of $a$. Now, let $\mathfrak{E}$ be a convex, origin symmetric ellipse with semi-major axis length $\sqrt{2p}$ and semi-minor axis length $\sqrt{p}$, so $\mathfrak{E}=\{(x,y)\in\mathbf{R}^2:x^2+2y^2<2p\}$. Then, we have $$Area(\mathfrak{E})=p\pi\sqrt{2}>4p=4\cdot Area(\mathfrak{F}).$$ Thus, by Minkowski there exists a lattice point $(j,k)\in\mathfrak{E}\setminus(0,0).$ By the above work, $p|j^2+2k^2$ and by definition of $\mathfrak{E}$, $j^2+2k^2<2p$. $j^2+2k^2$ is obviously positive, so $0<j^2+2k^2<2p$, so in order for $p|j^2+2k^2$ we must have $p=j^2+2k^2$, so we are done. $\Box$
For a proof involving unique factorization in $\mathbf{Z}[\sqrt{-2}]$, see here.
