Exercise 3.1.10 (When the congruence $x^2 \equiv 2 \pmod p$ has solutions?)

Proof. Let $p$ be an odd prime. Then $p=8k+r$, where $k$ is an integer, and $r\in \{1,3,5,7\}$. By Theorem 3.3,

• If the congruence $x^2\equiv 2(\mathit{mod}p)$ has solutions, then $\left(\frac{2}{p}\right)={(-1)}^{(p^2-1)∕8}=1$, thus $\frac{p^2-1}{8}$ is even. Therefore

  $$16\mid p^2-1={(8k+r)}^2-1=64k^2+16\mathit{kr}+r^2-1,$$

  which gives $16\mid r^2-1$. Since $16\nmid 3^2-1=8$ and $16\nmid 5^2-1=24$, we obtain $r=1$ or $r=7$, so

  $$p\equiv 1\text{ or }p\equiv 7(\mathit{mod}8).$$

• Conversely if $p\equiv 1\text{ or }p\equiv 7(\mathit{mod}8),$ then $r=1$ or $r=7$. Since $16\mid 1^2-1$, and $16\mid 7^2-1=48$, in both cases $16\mid r^2-1$, therefore

  $$16\mid {(8k+r)}^2-1=p^2-1,$$

  thus $2\mid \frac{p^2-1}{8}$, so that

  $$\left(\frac{2}{p}\right)={(-1)}^{(p^2-1)∕8}=1.$$

  This shows that the congruence $x^2\equiv 2(\mathit{mod}p)$ has solutions.

To conclude, if $p$ is an odd prime then $x^2\equiv 2(\mathit{mod}p)$ has solutions if and only if $p\equiv 1$ or $7(\mathit{mod}8)$. □