Expressing Integers as a Sum of Two Squares

Recall from the A Product of a Sum of Two Squares is a Sum of Two Squares page that if $m$ and $n$ are the sum of two squares then the product $mn$ is also a sum of two squares.

We will now look a bit further into the binary quadratic form:

(1)

\begin{align} \quad f(x, y) = x^2 + y^2 \end{align}

If $p$ is a prime then $p$ cannot necessarily be represented as a sum of two squares. For example, if $p = 3$ then there are no integers $x, y \in \mathbb{Z}$ such that $3 = x^2 + y^2$. To see this, observe that if $|x| \geq 2$ or $|y| \geq 2$ then $x^2 + y^2 \geq 4$. So $x, y \in \{ -1, 0, 1 \}$. It is easy to exhaust all cases to thus see that $3 \neq x^2 + y^2$ for any $x, y \in \mathbb{Z}$.

However, there are many primes that can be represented by $f(x, y)$. We aim to find all sum primes with the following propositions.

Proposition 1: There exists integers $x, y \in \mathbb{Z}$ such that $2 = x^2 + y^2$.

• Proof: If $x = 1$ and $y = 1$ then:

(2)

\begin{align} \quad 2 = 1^2 + 1^2 \quad \blacksquare \end{align}

Proposition 2: If $p$ is a prime and $p \equiv 3 \pmod 4$ then $p \neq x^2 + y^2$ for all $x, y \in \mathbb{Z}$. Moreover, $p^{2k + 1} \neq x^2 + y^2$ for all $x, y \in \mathbb{Z}$, $k \in \mathbb{N}$.

• Proof: Observe that $x^2 \equiv 0, 1 \pmod 4$ and $y^2 \equiv 0, 1 \pmod 4$ for all $x, y \in \mathbb{Z}$. Therefore $x^2 + y^2 \equiv 0, 1, 2 \pmod 4$. Since $p \equiv 3 \pmod 4$ it must be that $p \neq x^2 + y^2$ for all $x, y \in \mathbb{Z}$.

• Now if $k \in \mathbb{N}$ then observe that:

(3)

\begin{align} \quad p^{2k + 1} \equiv 3^{2k+1} \equiv 3 \pmod 4 \end{align}

• So it must be that $p^{2k+1} \neq x^2 + y^2$ for all $x, y \in \mathbb{Z}$. $\blacksquare$

Proposition 3: If $p$ is a prime and $p \equiv 3 \pmod 4$ then there exists integers $x, y \in \mathbb{Z}$ such that $p^2 = x^2 + y^2$. Moreover, there exists integers $x, y \in \mathbb{Z}$ such that $p^{2k} = x^2 + y^2$ for each $k \in \mathbb{N}$.

• Proof: If we let $x = p$ and $y = 0$ then clearly:

(4)

\begin{align} \quad p^2 = p^2 + 0^2 \end{align}

• Now if $k \in \mathbb{N}$ then let $x = p^k$ and $y = 0$. Then:

(5)

\begin{align} \quad p^{2k} = (p^k)^2 + 0^2 \quad \blacksquare \end{align}

Proposition 4: If $p$ is a prime and $p \equiv 1 \pmod 4$ then there exists integers $x, y \in \mathbb{Z}$ such that $p = x^2 + y^2$. Moreover, there exists integers $x, y \in \mathbb{Z}$ such that $p^k = x^2 + y^2$ for each $k \in \mathbb{N}$.

• Proof: Suppose that $p \equiv 1 \pmod 4$. Then we have that the Legendre symbol $\left ( \frac{-1}{p} \right ) = 1$. So $s^2 \equiv -1 \pmod p$ has a solution. Let:

(6)

\begin{align} \quad S = \left \{ x + sy : s^2 \equiv -1 \pmod p, \: 0 \leq x < \sqrt{p}, \: 0 \leq y < \sqrt{p} \right \} \end{align}

• Observe that $|S| > p$ but there are only $p$ possible residues of $x + sy$ modulo $p$. Therefore, by the pigeonhole principle there must exist $x + sy, u + sv \in S$ such that:

(7)

\begin{align} \quad x + sy = u + sv \pmod p \end{align}

• Therefore:

(8)

\begin{align} \quad (x - u) \equiv s(v - y) \pmod p \end{align}

• Squaring both sides yields:

(9)

\begin{align} \quad (x - u)^2 &\equiv s^2(v - y)^2 \pmod p \\ \quad (x - u)^2 &\equiv -1(v - y)^2 \pmod p \end{align}

• Therefore:

(10)

\begin{align} (x - u)^2 + (v - y)^2 \equiv 0 \pmod p \quad (*) \end{align}

• Since $0 \leq x, y, u, v < \sqrt{p}$ we must have that $(x - u)^2 + (v - y)^2 < 2p$. So the congruence at $(*)$ with this inequality implies that:

(11)

\begin{align} \quad p = (x - u)^2 + (v - y)^2 \end{align}

• Hence $p$ is the sum of two squares. Moreover, if $k \in \mathbb{Z}$ then $p^k$ is also the sum of two squares by the theorem mentioned at the top of the page. $\blacksquare$

Propositions 1-4 give us the building blocks which determine which integers can be expressed as a sum of two squares.

Theorem 5: If $n \in \mathbb{N}$ where $n = 2^{\alpha} p_1^{e_1}p_2^{e_2}...p_k^{e_k}q_1^{f_1}q_2^{f_2}...q_l^{f_l}$ where $p_i \equiv 1 \pmod 4$ for each $1 \leq i \leq k$ and $q_j \equiv 3 \pmod 4$ for each $1 \leq j \leq l$. Then there exists integers $x, y \in \mathbb{Z}$ such that $n = x^2 + y^2$ if and only if $f_j$ is even for each $1 \leq j \leq l$.

• Proof: The result follows immediately from propositions 1-4 and the fact that the product of a sum of two squares is also a sum of two squares. $\blacksquare$

For example, consider the number $n = 12250$. We have that:

(12)

\begin{align} \quad 12250 = 2^1 \cdot 5^3 \cdot 7^2 \end{align}

Observe that $5 \equiv 1 \pmod 4$ and $7 \equiv 3 \pmod 4$ but $2$ is even. So $12250$ can be written as the sum of two squares.