Exercise 2.1.56* (If $x^2 \equiv -2 \pmod p$, then $a^2 + 2b^2=p$ or $a^2 + 2b^2 = 2p$ has a solution)

Proof. (similar to the proof of Lemma 2.13.)

Let $p$ be a prime number, and suppose that $x$ is an integer such that $x^2\equiv -2(\mathit{mod}p)$.

We consider the set $A$ of ordered pairs $(u,v)$ of integers for which $u\le \lfloor \sqrt{p}\rfloor ,0\le v\le \lfloor \sqrt{p}\rfloor$:

where

and define

where ${[a]}_p$ denotes the class of $a\in \mathbb{Z}$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$.

The cardinality of $A={[[0,\lfloor \sqrt{p}\rfloor ]]}^2$ is

therefore $f$ cannot be injective (one to one). So there are two distinct ordered pairs $(u_1,v_1)$ and $(u_2,v_2)$ in $A$ such that $f(u_1,v_1)=f(u_2,v_2)$ (this is the pigeonhole principle described in the proof of lemma 2.13).

Then $u_1+x{v}_1\equiv u_2+x{v}_2(\mathit{mod}p)$, where $0\le u_1\le \lfloor \sqrt{p}\rfloor ,0\le u_2\le \lfloor \sqrt{p}\rfloor$. Take $a=u_1-u_2$ and $b=v_1-v_2$. Then $a\equiv -\mathit{xb}(\mathit{mod}p)$, thus $a^2\equiv x^2{b}^2(\mathit{mod}p)$, so $a^2+2b^2\equiv 0(\mathit{mod}p)$ since $x^2\equiv -2(\mathit{mod}p)$.

Since $(u_1,v_1)\ne (u_2,v_2)$, it follows that not both $a$ and $b$ vanish, so that $a^2+2b^2>0$.

Moreover, $u_1\le \lfloor \sqrt{p}\rfloor$ and $u_2\ge 0$, thus $a=u_1-u_2\le \lfloor \sqrt{p}\rfloor$. On the other hand, $u_1\ge 0$ and $u_2\le \lfloor \sqrt{p}\rfloor$, thus $a=u_1-u_2\ge -\lfloor \sqrt{p}\rfloor$. This shows that $|a|\le \lfloor \sqrt{p}\rfloor$. We obtain similarly $|b|\le \lfloor \sqrt{p}\rfloor$.

But $\sqrt{p}$ is never an integer, so $\lfloor \sqrt{p}\rfloor <\sqrt{p}$, therefore

This gives $a^2<p,b^2<p$, thus $a^2+2b^2<3p$:

This implies

At least one of the equations $a^2+2b^2=p$, $a^2+2b^2=2p$ has a solution. □