Fermat's Christmas Theorem

Theorem

Let $p$ be a prime number.

Then $p$ can be expressed as the sum of two squares iff:

• $p = 2$, or
• $p \equiv 1 \pmod 4$.

The expression of a prime of the form $4 k + 1$ as the sum of two squares is unique except for the order of the two summands.

Proof

Proof of Existence

There are three possibilities for a prime:

1. $p = 2$, or
2. $p \equiv 1 \pmod 4$, or
3. $p \equiv 3 \pmod 4$.

Sufficient Condition

Suppose $p$ can be expressed as the sum of two squares.

• First we note that $2 = 1^2 + 1^2$, which is the sum of two squares.

This disposes of the case where $p = 2$.

• Let $p = a^2 + b^2$.

From Square Modulo 4, either $a^2 \equiv 0$ or $a^2 \equiv 1 \pmod 4$. Similarly for $b^2$.

So $a^2 + b^2 \not \equiv 3 \pmod 4$ whatever $a$ and $b$ are.

So either $p = 2$, or $p \equiv 1 \pmod 4$.

Necessary Condition

• We have already noted that $2 = 1^2 + 1^2$, which is the sum of two squares.

• Let $p$ be a prime number of the form $p \equiv 1 \pmod 4$.

Suppose $m p = x^2 + y^2$ has a solution such that $1 < m < p$.

Let $u, v$ be the least absolute residues modulo $m$ of $x$ and $y$ respectively.

That is:

$\displaystyle u \equiv x, v \equiv y \pmod m: \frac {-m} 2 < u, v \le \frac m 2$

Then $u^2 + v^2 \equiv x^2 + y^2 \pmod m$.

Thus $\exists r \in \Z, r \ge 0: u^2 + v^2 = m r$.

We are going to establish a descent step.

That is, we aim to show that $r p$ is the sum of two squares with $1 \le r < m$.

First we show that $r$ does lie in this range.

If $r = 0$ then $u = v = 0$ and so $m$ divides both $x$ and $y$.

But then from $m p = x^2 + y^2$ we have that $m \backslash p$ which can't happen as $p$ is prime.

So:

$\displaystyle 1 \le r = \frac {u^2 + v^2} m \le \frac 1 m \times \left({\frac {m^2} 4 + \frac {n^2} 4}\right) = \frac m 2 < m$.

So $1 \le r < m$.

Now we show that $r p$ is the sum of two squares.

Multiplying $m p = x^2 + y^2$ and $m r = u^2 + v^2$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle m^2 r p\)	\(=\)	\(\displaystyle \left({x^2 + y^2}\right) \left({u^2 + v^2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({x u + y v}\right)^2 + \left({x v - y u}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Product of Sums of Two Squares

Now:

• $x u + y v \equiv x^2 + y^2 \equiv 0 \pmod m$, so $m \backslash x u + y v$
• $x v - y u \equiv x y - x y \equiv 0 \pmod m$, so $m \backslash x v - y u$

So, putting $m X = x u + y v, m Y = x v - y u$, we get:

$m^2 r p = m^2 X^2 + m^2 Y^2$

That is, $r p = X^2 + Y^2$.

Hence the descent step is established.

Next we need to show that $m p = x^2 + y^2$ has a solution for some $m$ with $1 \le m < p$.

From the First Supplement to the Law of Quadratic Reciprocity, we have that $-1$ is a quadratic residue for each prime $p \equiv 1 \pmod 4$.

Hence the congruence $x^2 + 1 \equiv 0 \pmod p$ has a least positive solution $x_1$ such that $1 \le x_1 \le p - 1$.

So there exists a positive integer $m$ such that $m p = x_1^2 + 1^2$.

This is just what we want, because:

$\displaystyle m = \frac {x_1^2 + 1^2} p \le \frac {\left({p-1}\right)^2 + 1} p = \frac {p^2 - 2\left({p-1}\right)^2} p < p$

If this solution has $m > 1$, then our descent step (above) guarantees a solution for a smaller positive value of $m$.

Eventually we will reach a solution with $m = 1$, that is:

$p = x^2 + y^2$

$\blacksquare$

Proof of Uniqueness

Let $p$ be prime such that $p \equiv 1 \pmod 4$.

Suppose $p = a^2 + b^2 = c^2 + d^2$ where $a > b > 0$ and $c > d > 0$.

We are going to show that $a = c$ and $b = d$.

From the two expressions for $p$, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({a d - b c}\right) \left({a d + b c}\right)\)	\(=\)	\(\displaystyle a^2 d^2 - b^2 c^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Difference of Two Squares
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({p - b^2}\right) d^2 - b^2 \left({p - d^2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	substituting for $a^2$ and $c^2$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p d^2 - b^2 d^2 - p b^2 + b^2 d^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \left({d^2 - b^2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	$\pmod p$

So we have:

$\left({a d - b c}\right) \left({a d + b c}\right) \equiv 0 \pmod p$

From Euclid's Lemma, that means $p \backslash \left({a d - b c}\right)$ or $p \backslash \left({a d + b c}\right)$.

So, suppose $p \backslash \left({a d + b c}\right)$.

Now, we have that each of $a^2, b^2, c^2, d^2$ must be less than $p$.

Hence $0 < a, b, c, d < \sqrt p$.

This implies $0 < a d + b c < 2p$.

That must mean that $a d + b c = p$.

But then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p^2\)	\(=\)	\(\displaystyle \left({a^2 + b^2}\right) \left({d^2 + c^2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a d + b c}\right)^2 + \left({a c + b d}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Product of Sums of Two Squares
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p^2 + \left({a c + b d}\right)^2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

That means $a c + b d = 0$

But since $a > b$ and $c > d$ we have $a c > b d$.

This contradiction shows that $a d + b c$ can not be divisible by $p$.

So this means $p \backslash \left({a d - b c}\right)$.

Similarly, because $0 < a, b, c, d < \sqrt p$ we have $-p < a d - b c < p$

This means $a d = b c$.

So $a \backslash b c$.

But $a \perp b$ otherwise $a^2 + b^2$ has a common divisor greater than $1$ and less than $p$ and it can't because $p$ is prime.

So by Euclid's Lemma $a \backslash c$.

So we can put $c = k a$ and so $a d = b c$ becomes $d = k b$.

Hence:

$p = c^2 + d^2 = k^2 \left({a^2 + b^2}\right) = k^2 p$

This means $k = 1$ which means $a = c$ and $b = d$ as we wanted to show.

$\blacksquare$

Historical Note

This theorem was initially stated without proof by Albert Girard in 1632.

Fermat announced its proof in a letter to Marin Mersenne dated December 25, 1640.

For this reason it is sometimes referred to as Fermat's Christmas Theorem.

It is also known as Fermat's Two Squares Theorem, or just the Two Squares Theorem.

Sources

• George F. Simmons: Calculus Gems (1992), Chapter $\text {B}.2$