Sums of 2 Squares (Fermat's Christmas Theorem)

Recall that in $\mathbb{Z}[\sqrt{n}]$, $N(\alpha)=a^2-nb^2$. What if $n$ was $-1$, so that we are working in $\mathbb{Z}[i]$? What are the possible norms that an element in $\mathbb{Z}[i]$ can have? Well, we know that norms are multiplicative, so let's see which primes can be norms, because we can multiply them to determine if a composite can be a norm.

First, let's state a theorem and its proof:

Minkowski's Convex Body Theorem In an $n$-dimensional lattice spanned by the $n$ vectors

$$\begin{gather} \nu_1=(k_{(1,1)},k_{(1,2)},\cdots,k_{(1,n)})\\ \nu_2=(k_{(2,1)},k_{(2,2)},\cdots,k_{(2,n)})\\ \vdots\\ \nu_n=(k_{(n,1)},k_{(n,2)},\cdots,k_{(n,n)})\\ \end{gather},$$ let $\Delta=\left\lvert\begin{matrix} k_{(1,1)}&k_{(1,2)}&\cdots&k_{(1,n)}\\ k_{(2,1)}&k_{(2,2)}&\cdots&k_{(2,n)}\\ \vdots&\vdots&\ddots&\vdots\\ k_{(n,1)}&k_{(n,2)}&\cdots&k_{(n,n)}\\ \end{matrix}\right\rvert$.

Then, if we have a convex region $R$ symmetric about the origin with volume greater than $2^n \Delta$, then there exists a non-zero point of the lattice in $R$.

Whew. That was a mouthful. Let's try a two-dimensional example to see what this is trying to show.

Let's take the vectors $\nu_1=(1,3)$ and $\nu_2=(4,-1)$. Then, the lattice looks like so:

Additionally, we have that the green region has area $\Delta=\left\lvert\begin{matrix}1&3\\4&-1\end{matrix}\right\rvert$. Thus, since all of the parallelograms have the same area, the region below has area $2^2\Delta=4\Delta$.

Minkowski's theorem states that if we have a convex region symmetric about the origin with area greater than $4\Delta$, then it will have a lattice point other than the origin. That seems reasonable enough. Let's try to prove the general case.

Suppose we have an $n$-dimensional lattice spanned by the vectors

$$\begin{gather} \nu_1=(k_{(1,1)},k_{(1,2)},\cdots,k_{(1,n)})\\ \nu_2=(k_{(2,1)},k_{(2,2)},\cdots,k_{(2,n)})\\ \vdots\\ \nu_n=(k_{(n,1)},k_{(n,2)},\cdots,k_{(n,n)})\\ \end{gather},$$ and let $\Delta=\left\lvert\begin{matrix} k_{(1,1)}&k_{(1,2)}&\cdots&k_{(1,n)}\\ k_{(2,1)}&k_{(2,2)}&\cdots&k_{(2,n)}\\ \vdots&\vdots&\ddots&\vdots\\ k_{(n,1)}&k_{(n,2)}&\cdots&k_{(n,n)}\\ \end{matrix}\right\rvert$.

Consider the region $S$ with the area greater than $2^n\Delta$. Consider the congruence classes $$\{(x_1,x_2,\cdots,x_n)+2\lambda_1\nu_1+2\lambda_2\nu_2+\cdots+2\lambda_n\nu_n\mid\lambda_i\in\mathbb{Z}\}.$$ Then, we know that each point in the region is congruent to a point in the region of area $2^n\Delta$. By the pidgeonhole principle, since the area of $S$ is greater than $2^n\Delta$, there exists two distinct points $A,B\in S$ such that $$\begin{gather} A=(x_1,x_2,\cdots,x_n)+2\alpha_1\nu_1+2\alpha_2\nu_2+\cdots+2\alpha_n\nu_n\\ B=(x_1,x_2,\cdots,x_n)+2\beta_1\nu_1+2\beta_2\nu_2+\cdots+2\beta_n\nu_n \end{gather}$$ Since $S$ is symmetric about the origin, we know that $-B\in S$, and then since $S$ is convex, the midpoint of $A$ and $-B$ is in $S$. Thus, $$\dfrac{A-B}{2}=(\alpha_1-\beta_1)\nu_1+(\alpha_2-\beta_2)\nu_2+\cdots+(\alpha_n-\beta_n)\nu_n.$$ Note that since $A$ and $B$ are distinct, at least one of $(\alpha_i-\beta_i)$ is non-zero, so we have found a non-zero lattice point in $S$. $\hspace{1cm}\Box$

Now let's state and prove Fermat's Christmas Theorem.

Theorem A prime $p$ is the sum of two squares if and only if $p\equiv 1\pmod{4}$.

---

Lemma If $p\equiv 1\pmod{4}$, then $-1$ is a quadratic residue modulo $p$. From the Legendre symbol or Euler's criterion, we know $(-1|p)=(-1)^{\frac{p-1}{2}}$. In order for $(-1|p)=1$ to be true, $\frac{p-1}{2}$ must be even. Thus, $\frac{p-1}{2}=2k$ for some $k$. Rearranging yields $p=4k+1$ for some $k$. Thus, if $p\equiv 1\pmod{4}$, then $-1$ is a quadratic residue modulo $p$.

---

Proof By our lemma, we know that there exists $u$ such that $u^2=-1\pmod{p}$. Consider the lattice spanned by the vectors $(1,u)$ and $(0,p)$. Note that every lattice point has a distance that is a multiple of $p$ from the origin: $$\begin{align} |a(1,u)+b(0,p)|&\equiv|(a,au+bp)|\\ &\equiv\sqrt{a^2+a^2u^2+2abup+b^2p^2}\\ &\equiv 0\pmod{p} \end{align}$$ Additionally, we have that $\Delta=\left\lvert\begin{matrix}1&0\\u&p\end{matrix}\right\rvert=p$. Now, consider the set of points $(x,y)$ such that $0\leq x^2+y^2<2p$. This is a convex region symmetric about the origin. We also know that this is a circle with radius $\sqrt{2p}$ and area $2\pi p$. Since we know $\pi>2$, we have $2\pi p>4p=4\Delta$. Thus, there must exist a point $(x,y)$ on the lattice such that $p\mid x^2+y^2$ and $0<x^2+y^2<2p$. However, this means that $x^2+y^2=p$, which is what we wanted to prove.$\hspace{1cm}\Box$

Now you might be thinking, Why did we prove Minkowski's Theorem for $n$-dimensions when we only needed it for two dimensions? Well, here, we use it in four dimensions!

$Q_2, P_1$ and $P_3$ : The Definition

So, let's take a look at what $Q_2, P_1$ and $P_3$ are.

$P_1$ and $P_3$

Well,

$P_1$ is the set of all prime numbers congruent to $1$ mod $4$.

$P_3$ is the set of all prime numbers congruent to $3$ mod $4$.

So, what about $2$? Well, this only even prime is the only prime not in $P_1$ and $P_3$.

$Q_2$

So, $Q_2$ is the set of positive integers that can be written as the sum of two squares of nonnegative integers.

Next part

$Q_2, P_1$ and $P_3$ : Some Simple Properties

Previous part

In this article, we'll look at the respectively properties of these sets.

$P_3$

We know that the set of primes are infinite. So, how about $P_3$? Is it infinite? How do we prove it?

We'll prove that $P_3$ is in fact, infinite. We argue by contradiction. Suppose not, then let $p_1 < p_2 < ... < p_k$ be the primes of $P_3$.

The hard part is to prove that $Q$ is prime. After all, why is it even true?

Note that if $Q$ is composite, then the prime factors of $Q$ must be congruent to $1$ mod $4$, as $Q$ is clearly not divisible by any of $p_1, p_2, ..., p_k$.

However, the product of any two numbers that are congruent to $1$ mod $4$ is congruent to $1$ mod $4$. Aha! So, we have a contradiction. Thus, $Q$ itself must be a prime (of the form $4k + 3$.)

However, $Q$ is clearly larger than $p_k$, so we obtain a contradiction.

$P_1$

Now, we'll prove again this set is infinite.

Consider $N = (n!)^2 + 1$ for all positive integers $n > 1$.

Let $p$ be the smallest prime divisor of $N$.

Since $N$ is odd, $p \neq 2$.

Clearly, $p > n$

So, if we can show that $p$ is of the form $4k + 1$, then we can replace $n$ by $p$ and repeat the argument to generate infinitely many primes in the form of $4k + 1$.

It remains to show that $p \equiv 1 \pmod{4}$.

Now, we have, $(n!)^2 \equiv -1 \pmod{p}$.

Thus, $(n!)^{p - 1} \equiv (-1)^{\frac{p - 1}{2}} \pmod{p}$.

However, Fermat's Little Theorem gives $(n!)^{p - 1} \equiv 1 \pmod{p}$.

So, $(-1)^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$.

Which clearly implies $p \equiv 1 \pmod{4}$.

as desired.

Now, we have show that $P_1$ and $P_3$ are infinite. What about $Q_2$?

$Q_2$

Now, what can we say about $Q_2$.

We'll prove that the product of any two elements of $Q_2$ is an element of $Q_2$.

Proof. Note the identity $(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2$. The claim follows immediately. $\blacksquare$.

Next part

$Q_2, P_1, P_3$ : Similarities and Differences

Previous part

So, we've introduced three seemingly bizarre sets. Now what? We'll prove two statements in this article. Firstly :

$Q_2 \cap P_3 = \emptyset$

Indeed, this is not hard to prove at all.

This immediately proves the claim.

Now we turn to the rather surprising and harder claim :

$P_1 \subset Q_2$

How many of you freak out when you see this. It's not a joke : It states that every prime number in the form of $4k + 1$ can be written as the sum of two squares. This is not easy to prove, but we'll show the proof below :

Here's a one-sentence proof from Wikipedia, but I'm going to show a more elementary proof. But first, we prove a crucial lemma.

(Thue). If $n$ is a positive integer and $a \perp n$, then there exists integers $0 < x, y \le \sqrt{n}$ such that $xa \equiv \pm y \pmod{n}$ for a suitable choice of the signs $+$ or $-$.

Consider all values of $xa - y$, with $0 < x, y \le \sqrt{n}$. Now, we have a list of $(\lfloor\sqrt{n}\rfloor + 1)^2 > n$ numbers and it follows by the pigeonhole principle that two of the numbers among them have the same remainder when divided by $n$. Let them be $ax_1 - y_1$ and $ax_2 - y_2$ respectively. We can clearly assume that $x_1 > x_2$. So, we can take $x = x_1 - x_2$ and $y = |y_1 - y_2|$. This proves the theorem.

With this theorem, the claim itself is not that hard.

Let us write $p = 4k + 1$ and we will prove that $p | (2k!)^2 + 1$. Since by Wilson's Theorem,

$-1 \equiv (p - 1)! \equiv 1 \cdot 2 \cdot ... \cdot (\frac{p - 1}{2}) \cdot (p - \frac{p - 1}{2}) \cdot ... \cdot (p - 1) \equiv (-1)^{\frac{p - 1}{2}} ((\frac{p - 1}{2})!)^2 \equiv ((2k)!)^2 \pmod{p}$.

Thus, letting $n = (2k)!$, we have $p \mid n^2 + 1$. By the theorem, there exists integers $0 < x, y < \sqrt{p}$ (since $\sqrt{p}$ is irrational) such that $p \mid n^2x^2 - y^2$ Since $p \mid n^2 + 1$, we have $p \mid x^2 + y^2$. Since $0 < x, y < \sqrt{p}$, $p = x^2 + y^2$. $\blacksquare$.

Next part

$Q_2, P_1$ and $P_3$ : The complete characterization of $Q_2$

Previous part

In this article, we'll completely characterize which numbers can be written as the sum of two squares and which numbers can't.

We call a number $a$ square-free if it $n^2 \nmid a$ for all positive integers $n > 1$.

Complete Characterization of $Q_2$

A number $n$ can be written as the sum of two squares if and only if the exponent of every prime congruent to $3$ modulo $4$ in the prime factorization of $n$ is even.

We'll present the proof.

Firstly, suppose that a number $n$ has the exponent of every prime congruent to $3$ modulo $4$ in its prime factorization even. Then we claim that it can be written as the sum of two squares.

Let $n = s^2m$, where $m$ is square-free. Note that $m$ is the product of primes in $P_1$ or $2$. Thus, each prime $p > 2$ dividing $n$ is in $P_1$. Now, since $P_1 \subset Q_2$ and the product of two elements in $Q_2$ is an element of $Q_2$, $n$ is in $Q_2$. (product of $s^2 + 0^2$, $1^2 + 1^2$s, and primes of $P_1$.) (See here if in doubt)

Now, suppose $n$ is the sum of two squares. Again, let $n = s^2m$, where $m$ is square-free. If $m = 1$, then $n = s^2$, and the conclusion is obvious. We need to prove that for every odd prime $p \mid m$, $p \in P_1$.

Let $n = x^2 + y^2$. Let $x = dx_1, y = dy_1$ where $d = \gcd(x, y)$. Then,

$n = d^2(x_1^2 + x_2^2) \Rightarrow \frac{s^2m}{d^2} = x_1^2 + x_2^2$.

Since $m$ is square-free, $d^2 \mid s^2$. Let $s^2 = td^2$ for some $t \in \mathbb{Z}$.

Then, $tm = x_1^2 + x_2^2$.

Since $p \mid m$, $p \mid x_1^2 = x_2^2$. Thus, $x_1^2 \equiv -x_2^2 \pmod{p}$.

Now, we show a useful fact :

If $p \in P_3$ such that $p \mid x^2 + y^2$, then $p \mid \gcd(x, y)$. Indeed, applying this into the problem gives that $p \in P_1$, as desired, since $\gcd(x_1, y_1) = 1$.

It remains to prove the fact :

Indeed, if $p \nmid \gcd(x, y)$, then by Fermat's Little Theorem,

$1 \equiv x^{p - 1} \equiv (x^2)^{\frac{p - 1}{2}} \equiv (-y^2)^{\frac{p - 1}{2}} \equiv (-1)^{\frac{p - 1}{2}}y^{p - 1} \equiv -1 \pmod{p}$, since $p \in P_3$. This is a contradiction. Thus, $p \mid \gcd(x, y)$.

Back to the original problem, this means that $p \in P_1$. But that is exactly what we wanted to prove. $\blacksquare$.

This should end your worries and doubts on when a number can be written as the sum of two squares.