Prime elements in $\mathbb{Z}[\sqrt{2}]$
In case someone is still interested in an elementary solution: By proceeding analogously to the case of $\mathbb{Z}[i]$ (in Neukirch's book on algebraic number theory) we can give a list that contains all prime elements of $\mathbb{Z}[\sqrt{2}]$. However, the solution is incomplete insofar that associated prime elements might appear more than once.
The corresponding theorem about the representability of integer primes as the norm of elements in $\mathbb{Z}[\sqrt{2}]$ is the following.
Lemma: For a prime number $p>2$, the diophantine equation \begin{equation*} p = a^2 - 2b^2 \end{equation*} is solvable in integers $a$ and $b$ if and only if $p \equiv 1$ or $7 \bmod 8$.
Note that $2 = 2^2-2*1^1$ is representable as well.
Proof: This is analogous to Neukirch's proof that a prime $p>2$ is representable as a sum of two squares if and only if $p \equiv 1 \bmod 4$. We replace Wilson's theorem (Theorem 80) by Theorem 95 in Hardy and Wrights classic book. It says that the congruence $x^2 \equiv 2 \bmod p$ has a solution if $p \equiv 1, 7 \bmod 8$ (two is a quadratic residue mod $p$).
Note that squares are $\equiv 0,1,4 \bmod 8$, hence only odd numbers $\equiv 1,7 \bmod 8$ can be represented by $a^2-2b^2$.
For the converse, by theorem 95, there is an integer $x$ such that $p\vert x^2-2 = (x-\sqrt{2})(x+\sqrt{2})$, so $p$ is no longer prime in $\mathbb{Z}[\sqrt{2}]$, since $p$ divides neither of the factors in $\mathbb{Z}[\sqrt{2}]$. Hence $p$ can be written as the product $\alpha \beta$ of two non-units, such that for the norm $N(p) = p^2 = N(\alpha) N(\beta)$ holds. Since $\alpha$ and $\beta$ are non-units, $N(\alpha) = N(\beta) = p$ (up to a possible minus sign of which we can get rid of by choosing appropriate associate elements). If we write e.g. $\alpha = a+bi$, we found the integers $a$ and $b$ with $N(\alpha) = a^2 - 2b^2 = p$.
Now the prime elements of $\mathbb{Z}[\sqrt{2}]$ (up to, and possibly including) associates are
- $\sqrt{2}$,
- $\alpha \in \mathbb{Z}[\sqrt{2}]$ such that $N(\alpha) = p$ is a prime $p \equiv 1, 7 \bmod 8$,
- and integer primes $p \equiv 3,5 \bmod 8$.
Now, one can use the proof as for the prime elements in $\mathbb{Z}[i]$ almost word by word by first showing that all these elements are in fact prime elements, and then by showing that any prime element must be associated to an element in the list. (Elements of prime norm are prime because they cannot be further factorized in non-units (and using that we work in an UFD here), and elements in (3) with square prime norm are prime because they are not representable) (any prime element has norm in $\mathbb{Z}$ which factorizes there uniquely. Then one can say again that the prime element must have norm $\pm 1$, $\pm p$ or $\pm p^2$, for $p$ being one of the primes dividing the norm in $\mathbb{Z}$. $\pm 1$ cannot be, $\pm p$ and we are in case (1) or (2), and $\pm p^2$ gives case (3) ).
This is a partial (unsatisfyingly partial) answer:
There is a nice theorem in algebraic number theory:
Theorem(Dedekind): Let $\mathcal{O}_K$ be a number ring such that there exists $\alpha\in\mathcal{O}_K$ with $\mathcal{O}_K=\mathbb{Z}[\alpha]$. Let $f(T)$ be the minimal polynomial of $\alpha$ over $\mathbb{Q}$. Then, for every prime $p\in\mathbb{Z}$ let $\overline{g_1(T)}^{e_1}\cdots \overline{g_m(T)}^{e_m}=\overline{f(T)}$ be the prime factorization of $\overline{f(T)}\in\mathbb{F}_p[T]$ (where $g_i(T)\in\mathbb{Z}[T]$). Then, the prime ideals of $\mathcal{O}_K$ lying over $p$ are those of the form $(p,g_i(\alpha))$ for $i=1,\ldots,m$.
So, now we have the case when $K=\mathbb{Q}(\sqrt{2})$, $\alpha=\sqrt{2}$, and $f(T)=T^2-2$. Thus, the find the prime ideal of $\mathbb{Z}[\sqrt{2}]$ lying above $p$ we need only factor $T^2-2$ in $\mathbb{F}_p[T]$. Now, by quadratic reciprocity we know that $2$ has a square root in $\mathbb{F}_p$ if and only if $p\equiv 1,7\mod 8$.
If $p\equiv 3,5\mod 8$ then $T^2-2$ is irreducible in $\mathbb{F}_p[T]$ and thus the prime ideal lying above $p$ is $(p,(\sqrt{2})^2-2)=(p)$.
If $p\equiv 1,7\mod 8$ then we know that $T^2-2$ factors in $\mathbb{F}_p[T]$ as $(T-\beta)(T+\overline{\beta})$ where $\beta$ is some (lift to $\mathbb{Z}$ of a) square root of $2$ in $\mathbb{F}_p$. Thus, Dedekind's theorem tells us that the prime ideals of $\mathbb{Z}[\sqrt{2}]$ lying above $p$ are $(p,\sqrt{2}\pm\beta)$. Now, abstractly we know then that $(p,\sqrt{2}\pm\beta)=\text{gcd}(p,\sqrt{2}\pm\beta)$, and that this gcd can be computed (in theory) using the Euclidean algorithm.
Thus, up to units of $\mathbb{Z}[\sqrt{2}]$ (which are all of the form $\pm(1-\sqrt{2})^n$, $n\in\mathbb{Z}$) the prime elements of $\mathbb{Z}[\sqrt{2}]$ are $p$ for $p\equiv 3,5\mod 8$, and $\text{gcd}(p,\sqrt{2}\pm\beta)$ where $\beta$ is a lift of a square root of $2$ in $\mathbb{F}_p$.