Integers of the form $x^2+2y^2$

I found the picture of this problem and my solution while scrolling through Google Photos (I was bored at LAX waiting for my flight). I don't vividly remember when and what it was for, but it must have been a part of my math olympiad practice, given that it is a typical math olympiad-y number theory problem and the picture was taken and uploaded when I was in high school.

I do remember, however, struggling and spending a lot of time on this problem. I think it is worth going over it again for fun.

Problem Statement

Problem. Find all integers of the form $x^2 + 2y^2$ where $x,y \in \mathbb{Z}$.

Lemma 1

Lemma 1. Let $p$ be a prime number that divides $x^2 + 2y^2$. If $p \equiv 5$ or $7 \; (\textrm{mod } 8)$, then $p$ divides both $x$ and $y$.

Proof of Lemma 1. Suppose $p \not\mid x$. Then $p \not\mid y$ because $p \mid x^2 + 2y^2$ and so modular inverse of $x$ and $y$ in $\text{mod } p$ exist. Let $y^{-1}$ denote the inverse of $y$. Then,

\[ \begin{align*} x^2 + 2y^2 \equiv 0 \; (\textrm{mod } p) & \iff x^2 \equiv -2y^2 \; (\textrm{mod } p) \\ & \iff (x y^{-1})^2 \equiv -2 \; (\textrm{mod } p) \end{align*} \]

However (here, $( \frac{a}{p} )$'s are the Legendre/Jacobi symbols),

\[ \begin{align*} \left( \frac{-2}{p} \right) & = \left( \frac{-1}{p} \right) \left( \frac{2}{p} \right) && (\because \textsf{Properties of Legendre symb.}) \\ & = \left( -1 \right)^{\frac{p-1}{2}} \left( \frac{2}{p} \right) && (\because \textsf{Euler's criterion}) \\ & = \left( -1 \right)^{\frac{p-1}{2}} \left( -1 \right)^{\frac{p^2-1}{8}} && (\because \textsf{Gauss' Lemma}) \\ & = \left( -1 \right)^{\frac{p^2 + 4p - 5}{8}} \\ & = \left( -1 \right)^{\frac{(p+5)(p-1)}{8}} \end{align*} \]

So if $p$ was of the form $p = 8k+5$ for some $k \in \mathbb{Z}$,

\[ \left( \frac{-2}{p} \right) = \left( -1 \right)^{\frac{2(4k+5)(8k+4)}{8}} = \left( -1 \right)^{(4k+5)(2k+1)} = -1 \]

and if $p$ was of the form $p = 8k+7$ for some $k \in \mathbb{Z}$,

\[ \left( \frac{-2}{p} \right) = \left( -1 \right)^{\frac{(8k+12)(8k+6)}{8}} = \left( -1 \right)^{(2k+3)(4k+3)} = -1 \]

Hence, if $p \equiv 5$ or $7 \; (\textrm{mod } 8)$, the solution to $X^2 \equiv -2 \; (\textrm{mod } p)$ does not exist, which contradicts the assumption that $p \not\mid x$. Therefore, if $p \equiv 5$ or $7 \; (\textrm{mod } 8)$, then $p \mid x$ and, as $p \mid x^2 + 2y^2$, we also have $p \mid y$. $\quad \square$

Lemma 2

Lemma 2. The multiple of two integers of the form $a^2 + 2b^2$ is also an integer of the form $a^2 + 2b^2$ where $a,b \in \mathbb{N}\cup \{0\}$.

Proof of Lemma 2. Let $a,b,c,d \in \mathbb{N}\cup \{0\}$. \[ \begin{align*} (a^2 + 2b^2) (c^2 + 2d^2) & = (a^2 c^2 + 4 b^2 d^2) + 2(b^2 c^2 + a^2 d^2) \\ & = (a^2 c^2 + 4 abcd + 4b^2 d^2) + 2 (b^2 c^2 - 2abcd + a^2 d^2) \\ & = (ac+2bd)^2 + 2(bc-ad)^2 && \hspace{-1.5cm} \square \end{align*} \]

Lemma 3

Lemma 3. Let $p$ be a prime of the form $p \equiv 1,2,$ or $3 \; (\textrm{mod } 8)$. There exist nonnegative integers $a$ and $b$ such that $p = a^2 + 2b^2$.

Proof of Lemma 3. The only prime of the form $p \equiv 2\; (\textrm{mod } 8)$ is $p = 2$ which is $2 = 0^2 + 2 \cdot 1^2$.

Consider the case where $p \equiv 2\; (\textrm{mod } 8)$. Let $k := \lceil \sqrt{p} \rceil + 1$ and

\[ S_a := \{ ax+y \mid 0 \leq x, y \leq k-1 \} \]

It is clear that $\lvert S_a \rvert = k^2 > p$. So by the pigeonhole principle, there exists two distinct pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that

\[ ax_1 + y_1 \equiv ax_2 + y_2 \; (\textrm{mod } p) \] which is equivalent to \[ a(x_1 - x_2) + (y_1 - y_2) \equiv 0 \; (\textrm{mod } p) \] Denote $x_0 := x_1 - x_2$ and $y_0 := y_1 - y_2$. Then $0 < \lvert x_0 \rvert \leq k-1$ and $0 < \lvert y_0 \rvert \leq k-1$ and hence $a \lvert x_0 \rvert + \lvert y_0 \rvert \in S_a$ and $a \lvert x_0 \rvert + \lvert y_0 \rvert \equiv 0$ $\;(\textrm{mod } p)$. That is, $x$ and $y$ that satisfies the congruence $ax \equiv y \; (\textrm{mod } p)$ exists in the range: \[ 0 \leq x,y \leq k-1 = \lceil \sqrt{p} \rceil < \sqrt{p} \] Meanwhile, as we have seen in the proof of Lemma 1 already, \[ \begin{align*} \left( \frac{-2}{p} \right) = \left( -1 \right)^{\frac{(p+5)(p-1)}{8}} \end{align*} \] Hence, if $p \equiv 1$ or $3 \; (\textrm{mod } 8)$, then $( \frac{-2}{p}) = 1$ and so there exists $a$ such that $a^2 \equiv -2 \; (\textrm{mod } p)$. Given such an $a$, and for $x$ and $y$ such that $ax \equiv y \; (\textrm{mod } p)$, \[ \begin{align*} ax \equiv y \; (\textrm{mod } p) & \iff a^2 x^2 \equiv y^2 \; (\textrm{mod } p) \\ & \iff -2x^2 \equiv y^2 \; (\textrm{mod } p) \\ & \iff 2x^2 + y^2 \equiv 0 \; (\textrm{mod } p) \end{align*} \] As $0<x,y<\sqrt{p}$, we get $0<2x^2+y^2<3p$ and so the only possibilities are $2x^2 +y^2 = p$ and $2p$.

• If $2x^2 + y^2 = 2p$, then $y^2 = 2(p - x^2)$ is even and hence $y$ must be even. Substituting $y = 2y'$ gives us \[ 2x^2 + y^2 = 2x^2 + 4y'^2 = 2p \iff x^2 + 2y'^2 = p \] Hence, $p$ can be written in a form of $a^2 + 2b^2$.
• If $2x^2 + y^2 = p$, then $p$ is already in a form of $a^2 + 2b^2$, whence the statement.

Therefore, for all primes $p$ such that $p \equiv 1,2,3 \; (\textrm{mod } 8)$, there exist non-negative integers $a$ and $b$ such that $p = a^2 + 2b^2$. $\quad \square$

Solution

Now we provide the solution to the problem.

Solution. Denote $x^2 + 2y^2 = n$ and represent $n = ms^2$ where $m, s \in \mathbb{N}$ and $m$ is square-free.

Define the following two subsets of $\mathbb{N}$: \[ \begin{align*} A & = \{ n \mid n = ms^2 \textsf{ where } m, s \in \mathbb{N}, m \textsf{ is square-free,} \\ & \qquad \qquad \textsf{ and } p \not\equiv 5,7 \; (\textrm{mod } 8) \textsf{ for all prime } p \textsf{ s.t. } p \mid m, \} \\ \tilde{A} & = \{ x^2 + 2y^2 \mid x,y \in \mathbb{N} \cup \{0\} \} \end{align*} \] We shall prove $A = \tilde{A}$.

Step 1: $\tilde{A} \subseteq A$.

We first prove that if $p^\alpha \| x^2 + 2y^2$ for some $\alpha \in \mathbb{N} \cup \{0\}$ and $p \equiv 5, 7$ $(\textrm{mod } 8)$, then $2 \mid \alpha$. Here, $p^x \| n$ is the notation for the maximum $x$ such that $p^x \mid n$ yet $p^{x+1} \not\mid n\;$ (i.e., $p$-adic order of $n$).

Assume for the sake of contradiction that $\alpha$ is odd, i.e. $\alpha = 2k+1$ where $k \in \mathbb{N} \cup \{0\}$.

Claim 1. $p^n \mid x,y$ for all $n \leq k+1$.

Proof of Claim 1. We prove by mathematical induction.

• Base case: When $n = 0$. $p^n = 1 \mid x,y$ and hence the statement holds.
• Inductive hypothesis: Suppose that $p^\ell \mid x,y$ for some $\ell \leq k$.
• Inductive step: Suppose that the inductive hypothesis is true, i.e. $p^\ell \mid x,y$ where $\ell \leq k$. Then since $k-\ell \geq 0$, \[ \begin{align*} p \mid p^{2(k-\ell) + 1} \; \| \left( \frac{x}{p^\ell} \right)^2 + 2 \left( \frac{y}{p^\ell} \right)^2 \end{align*} \] This implies \[ \begin{align*} p \mid \left( \frac{x}{p^\ell} \right)^2 + 2 \left( \frac{y}{p^\ell} \right)^2 & \implies p \mid \frac{x}{p^\ell}, \frac{y}{p^\ell} && (\because \textsf{Lemma 1}) \\ & \implies p^{\ell + 1} \mid x, y \end{align*} \] Therefore, if $p^\ell \mid x,y$ then $p^{\ell + 1} \mid x,y$. This proves the claim. $\quad \square$

By Claim 1, $p^{n} \mid x,y$ for all $n \leq k+1$, and so we know $p^{k+1} \mid x,y$ which makes $p^{2k+2} \mid x^2, y^2$. Then $p^{2k+2} \mid x^2 + 2y^2$, but this contradicts the fact that $p^{2k+1} \| x^2 + 2y^2$. Hence, $\alpha$ cannot be odd.

Consequentially, for all $p$ such that $p \equiv 5, 7 \; (\textrm{mod } 8)$ has an even power in $n$, hence goes into the $s$ term in $n = ms^2$; more precisely, for any $n \in \tilde{A}$, if $n$ were to represented as $n = ms^2$, if $p \equiv 5,7 \; (\textrm{mod } 8)$ then $p \not\mid m$. Therefore, $n \in A$ and hence $\tilde{A} \subseteq A$.

Step 2: $\tilde{A} \supseteq A$.

For any $n = ms^2 \in A$, let $m = p_1 p_2 \cdots p_k$. By definition of $A$, all $p_i$'s are $p_i \equiv 1,2,3 \; (\textrm{mod } 8)$, and so by Lemma 3, there exist $a_1, b_1,\dots, a_k, b_k$ $\in \mathbb{N} \cup \{0\}$ such that \[ p_1 = a_1^2 + 2b_1^2, \; p_2 = a_2^2 + 2b_2^2, \; \dots, \; p_k = a_k^2 + 2b_k^2 \] Then by Lemma 2, there exists $a_t, b_t \in \mathbb{N} \cup \{0\}$ such that \[ m = p_1p_2 \cdots p_k = (a_1^2 + 2b_1^2) \cdots (a_k^2 + 2b_k^2) = a_t^2 + 2b_t^2 \] Therefore, $ms^2 = (s a_t)^2 + 2(s b_t)^2$, making $n = ms^2 \in \tilde{A}$ as well. This proves $A \subseteq \tilde{A}$.

Step 3: $x=y=0$.

In this case, trivially $x^2 + 2y^2 = 0$.

Conclusion

From Step 1 and 2, we conclude that $A = \tilde{A}$. Step 3 suggests that $0$ must be included in $A$. All in one, we conclude the following:

An integer $n$ is of the form $x^2 + 2y^2$ iff $n = ms^2$ where $m, s \in \mathbb{N} \cup \{0\}$ then all prime divisors $m$ must not be congruent to $5$ and $7$ in $\textrm{mod } 8$ (i.e., every prime divisor of $n$ that are congruent to $5$ or $7$ in $\textrm{mod } 8$ must be in a power of an even number).