dealing with sum of squares (1) I need to be able to conclude that there are $a, b \in \Bbb Z$, not 0, such that $|a| < √p,\ |b| < √p$
and $$a^2 + 2b^2 ≡ 0\ (mod\ p)$$
I'm not sure how to go about this at all.  But apparently it is supposed to help me show (2) that 
there are $a, b \in \Bbb Z$, such that either $$a^2 + 2b^2 = p$$ or $$a^2 + 2b^2 = 2p$$
Any idea how to go about 1 or 2?
 A: Assuming $(a\cdot b,p)=1,$
$$a^2\equiv-2b^2\pmod p\implies (a\cdot b^{-1})^2\equiv-2\pmod p$$
Now, using Legendre Symbol, $$\left(\frac{-2}p\right)=\left(\frac{-1}p\right)\left(\frac2p\right)$$
Also from here, $$\left(\frac{-1}p\right)=1\text{ iff }p\equiv1\pmod 4$$ and $$\left(\frac2p\right)=1\text{ iff }p\equiv\pm1\pmod 8$$
A: Assuming $p$ is a prime and you have at least one solution for $\tilde{a}^2 + 2 \tilde{b}^2 \equiv 0 \pmod p$ where $\tilde{b} \not\equiv 0 \pmod p$. Let $u = \tilde{a}\tilde{b}^{-1} \pmod p$, we have $u^2 + 2 \equiv 0 \pmod p$. 
(By lab bhattacharjee's answer, such $u$ exists when $p$ is a prime of the form $8k+1$ or $8k+3$)
Let $\mathscr{L} \subset \mathbb{Z}^2$ be the lattice of integer points $\left\{ ( u x + p y, x ) : x, y \in \mathbb{Z}^2 \right\}$ and $\mathscr{D}$ be its fundamental domain. 
Pick a real number $L$ such that $\sqrt{p} < L < \lceil\sqrt{p}\rceil$ and let $\mathscr{R} \subset \mathbb{R}^2$
be the square $[-L,L]^2$. 
Since $\mathscr{R}$ is convex, symmetric with respect to the origin and its area satisfy:
$$\operatorname{Area}(\mathscr{R}) = 4 L^2 > 4 p = 4 \operatorname{Area}(\mathscr{D})$$
By Minkowski's theorem, $ \mathscr{L} \cap \mathscr{R} $ contains an non-zero element. i.e. there exists $x, y \in \mathbb{Z}^2$, not both zero, such that:
$$| ux + py | < L \quad\text{ and }\quad |x| < L$$
Since $|ux + py|, |x|$ are integers and $\sqrt{p} > \lfloor L\rfloor$, we in fact have:
$$| ux + py | < \sqrt{p} \quad\text{ and }\quad |x| < \sqrt{p}$$
Let $a = ux + py$ and $b = x$, we have:
$$a^2 + 2b^2 = (u x + p y)^2 + 2 x^2 = (u^2 + 2) x^2 + p (2u x y + p y^2) \equiv 0 \pmod p$$
and 
$$0 < a^2 + 2b^2 < p + 2p \implies a^2 + b^2 = p \,\text{ or } 2p$$
A: Hint $\ $ Apply the following result of Aubry-Thue

A: Some ideas: for $\,a,b,\in\Bbb F_p^*\,$ :
$$a^2+2b^2=0\pmod p\iff -2=x^2\pmod p\iff 1=\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)\iff$$
$$p=1,3\pmod 8\;\;(\text{why?})$$
For example, with $\,p=7\,\;$ we get
$$\left(\Bbb F_7^*\right)^2=\{1,2,4\}\;,\;\;2\cdot\left(\Bbb F_7^*\right)^2=\{1,2,4\}\implies a^2+2b^2\neq0\pmod 7\;\;\forall\;a,b\in\Bbb F_7^*$$
but with $\,p=11\,$ we get
$$\left(\Bbb F_{11}^*\right)^2=\{1,4,9,5,3\}\;,\;\;2\cdot\left(\Bbb F_{11}^*\right)^2=\{2,8,7,10,6\}$$
and we certainly have several (how many?) solutions: 
$$1^2+2\cdot4^2=0\pmod{11}\;,\;\;2^2+2\cdot 3^2=0\pmod{11}\;,\;\;etc.$$
