Express a prime $p$ as $p=a^2-2b^2$ Suppose $2$ is a quadratic residue modulo $p$ for an odd prime $p$. That is, there is an element $u$ such that $u^2 \equiv 2 \pmod{p}$.
From here, can we prove that there exist integers $a$ and $b$ such that 
$$a^2-2b^2=p$$
Its the equality part that is tricky. It is trivial to produce $a,b$ where $a^2-2b^2 \equiv 0 \pmod{p}$, for example when $a=u, b=1$. Is there some way of starting with $(u,1)$ and constructing $(a,b)$ from it? If not constructing algorithmically, is there at least an existential argument?
This is related to the problem of finding for which primes $p$ is $2$ a quadratic residue. If we can prove the above, then from the form of $p=a^2-2b^2$, it is easy to see that $p=8k \pm 1$.
I know a proof which uses quadratic fields. It shows that $p$ cannot be prime in $\mathbb{Z}[\sqrt{2}]$ and thus it is of the form $p=(a+\sqrt{2}b)(a-\sqrt{2}b)$. However, it seems (to me) like an overkill to use non-trivial results from quadratic fields for this. Surely there's got to be an elegant method which stays within $\mathbb{Z}/p\mathbb{Z}$ 
 A: I don't know much about field theory but within the laws of elementary mathematics, note that by Thue's Lemma we have $$x \equiv uy \pmod p$$ For $u^2 \equiv 2 \pmod p$, such that $0<|x|,|y|<\sqrt{p}$. 
Then proceed to notice $$x^2-2y^2 \equiv 0 \pmod p$$ Then notice $$-2p<x^2-2y^2<p$$
So $x^2-2y^2=0$ or $x^2-2y^2=-p$. I believe you can proceed from here.  
If you actually want to see the full solution, pass your mouse over the yellow area. 

 $x^2-2y^2=0$ is clearly impossible over the integers. If $x^2-2y^2=-p$, then $$(2y-x)^2-2(y-x)^2=2y^2-x^2=p$$

A: This is a general algorithm to take a prime, in particular an odd prime $p,$ and express it as the value of an indefinite binary form of discriminant $\Delta.$ The requirements are that $\Delta > 0,$ that $\Delta $ is NOT a perfect square, and that $\Delta$ is a quadratic residue $\pmod p.$ In particular, $p$ does not divide $\Delta.$ With large class number, this method also tells us which forms represent $p,$ as any prime is represented either by one $SL_2 \mathbb Z$ equivalence class of forms of a specified discriminant $\Delta,$ or by a class and its opposite class. This algorithm is very fast once programmed,  similar to the Euclidean algorithm. As a fairly difficult example, take some prime $p$ such that $(257|p) = 1.$ Then $p$ is represented either by the principal form $\langle 1, 15, -8 \rangle,$ or by both of a pair of opposite forms, $\langle 2, 15, -4 \rangle$ and $\langle 4, 15, -2 \rangle.$ Deciding which is the stuff of Class Field Theory, but we can find out, for a specific prime, with the algorithm below. Well, why not. A prime $p$ other than $257$ can be expressed as $p = u^2 + 15 uv - 8v^2$ if and only if $x^3 - x^2 - 4x+3$ has three distinct roots $\pmod p.$ We also have $x^3 - x^2 - 4x+3 \equiv (x+9)^2 (x + 238) \pmod {257},$ and $257$ is also represented by  $ u^2 + 15 uv - 8v^2.$ A prime $p,$ including $2,$ is represented as  $p = 2u^2 + 15 uv - 4v^2$ if and only if  $x^3 - x^2 - 4x+3$ is irreducible $\pmod p.$ Oh, $x^3 - x^2 - 4x+3$ has exactly one root $\pmod p$ when $(257|p) = 1.$ Since the Fermat prime $257 \equiv 1 \pmod 4,$ we also have $(257|p) = (p|257).$
$$ (2u)^2 \equiv 8 \pmod {4p}, $$
$$ (2u)^2 = 8 + 4pt $$
for an integer $t.$ This means that the binary quadratic form 
$\langle p, 2u, t \rangle,$ or
$$ f(x,y) = p x^2 + 2 u xy + t y^2,  $$
has discriminant $8.$ 
Reduction of this form to a Gauss-Lagrange "reduced" form takes a finite number of steps. There is just one equivalence class of forms of this discriminant, and just two reduced forms, $\langle 1,2,-1 \rangle$ and $\langle -1,2,1 \rangle.$
The process of reduction, done carefully, results in an integer matrix $P$ of determinant $1$ such that, for example, $P^T HP = G,$ where
$$
H =
\left(
\begin{array}{rr}
p & u \\
u & t
\end{array}
\right)
$$ 
and, as one of the two choices,
$$
G =
\left(
\begin{array}{rr}
1 & 1 \\
1 & -1
\end{array}
\right)
$$
We then have $Q = P^{-1}$ is also an integer matrix of determinant $1,$ and
$$ Q^T GQ = H. $$ The left hand column of $Q$ tells us how to represent $p$ as $a^2 + 2ab - b^2.$ 
Probably worth it: reduction is a finite sequence of steps, beginning with $H_0 = H$ and $H_{j+1} = R_j^T H_j R_j,$ finally some $H_N = G$ is reduced. A careful reading of the Buell pages reveals that we always have
$$
R_j =
\left(
\begin{array}{rr}
0 & -1 \\
1 & \delta_j
\end{array}
\right)
$$
with integer $\delta_j.$ The bookkeeping part is $P = R_0 R_1 R_2 \cdots R_{N-1}.$
Oh, before I forget, it turns out that an indefinite form $\langle A,B,C \rangle$ is reduced if and only if BOTH $AC<0$ and $B>|A+C|.$ This is a minor note in a book in preparation by Franz Lemmermeyer. Here we go, Gauss reduced forms are Theorem 1.36, pdf page 43 but book numbered page 37. The condition I give above is formula (1.34).
I made jpegs of the three most important pages in BUELL as relates to reduction of indefinite binary forms. 



