# 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)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:

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:

- 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:

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

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:

- 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:

- Therefore:

- Squaring both sides yields:

- Therefore:

- 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:

- 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)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.