From Fermat's Last Theorem, Part 7: Fermat's Sum of Two Squares Theorem

从费马大定理谈起（七）：费马平方和定理 苏剑林 · 2014-08-23 · Mathematics prime number number theory fermat's last theorem

I had originally planned to start preparing the proof for n=3, but that requires introducing the notion of Eisenstein integers, whereas we've already introduced the Gaussian integers, and haven't yet properly shown the reader just how beautiful they are. From the two proofs of the n=4 case, we know that the point of introducing Gaussian integers is to fully factor expressions such as $z^n-y^n$. However, that alone doesn't really display much of the magic of Gaussian integers. As readers may already know, many simple results in complex analysis, if described purely in terms of real numbers, come across as astonishingly clever feats of ingenuity — and the same is true in number theory involving Gaussian integers. In this post, let's think through Fermat's sum of two squares theorem, so as to once again appreciate the convenience that Gaussian integers bring to certain problems in number theory. We start from Fermat's Last Theorem, but we won't be talking only about Fermat's Last Theorem.

Fermat's Sum of Two Squares Theorem: an odd prime $p$ can be written as the sum of two integer squares if and only if it has the form $4k+1$, and, up to the order of summation, this representation is unique.

There are quite a few proofs of this theorem that stay purely within the real integers, but most of them leave you thinking "how on earth would anyone have thought of that step!" For those familiar with Gaussian integers, however, the proof within $\mathbb{Z}[i]$ is probably the most natural one. This theorem is not merely a statement about real integers — it also determines which real primes remain prime in the Gaussian integers. It tells us that real primes of the form $4k+1$ are not Gaussian primes, while primes of the form $4k+3$ are Gaussian primes.

Lemma

Without further ado, let's prove Fermat's sum of two squares theorem. Before proving the theorem, we first need to prove the following lemma:

If $p$ is a prime of the form $4k+1$, then there exists an integer $x$ such that $p|x^2+1$.

Note that this lemma holds entirely within the real integers $\mathbb{Z}$. We'll postpone the proof of this lemma and first see directly how it lets us quickly prove the sum of two squares theorem.

By the lemma, in $\mathbb{Z}[i]$ we have $p|(x+i)(x-i)$. If $p$ were a Gaussian prime (that is, if the theorem failed), then $p|x+i$ or $p|x-i$ would have to divide it, but $\frac{x\pm i}{p}=\frac{x}{p}\pm\frac{1}{p}i$, and the latter is not a Gaussian integer, which is a contradiction. So $p$ is composite in $\mathbb{Z}[i]$. In fact, the crux of the proof is already done; what follows is mostly a matter of careful bookkeeping. Let $p=uv$, $N(u),N(v) > 1$, then

$$p^2=N(p)=N(u) N(v)$$

From this $N(u)|p^2$; since the norm is an operation valued in the real integers, we must have $N(u)=p$. It follows that $N(v)=N(u)=p$, but $u\neq v$, so they can only be conjugate to one another. We may therefore write $u=a+bi,v=a-bi$, with $a,b$ real integers, and then

$$p=(a+bi)(a-bi)=a^2+b^2$$

Next we prove uniqueness. Suppose $p$ has two distinct representations:

$$p=a^2+b^2=c^2+d^2$$

Then we get $(a+bi)(a-bi)=(c+di)(c-di)$, i.e. $(a+bi)|(a+di)(c-di)$. If $a+bi$ is a Gaussian prime, then either $a+bi|c+di$ or $a+bi|c-di$, giving correspondingly either $a-bi|c-di$ or $a-bi|c+di$. Hence $a+bi$ and $c+di$ differ by at most a unit factor, so $a^2+b^2=c^2+d^2$ is in fact one and the same representation, differing only possibly in the order of the summands. If $a+bi$ is not a Gaussian prime, then $a+bi=s t$, and

$$p=(a+bi)(a-bi)=st\bar{s}\bar{t}=(s\bar{s})(t\bar{t})$$

which splits $p$ into a product of two real integers each greater than 1, contradicting the fact that $p$ is prime.

Finally, we only need to show that primes of the form $4k+3$ cannot be written as a sum of two squares. This is easy — it suffices to consider congruence mod 4 — so we'll skip it.

Proof

However, it may come as a surprise that proving the lemma is not particularly easy. A complete proof of the lemma requires the notion of a "prime field": for a prime $p$, the residues $\{1,2,\dots,p-1\}$ modulo $p$ form a field, called the prime field, on which one can add, subtract, multiply, and divide just as with the real numbers. This post won't give the full proof of this part; interested readers need only consult any textbook on elementary number theory. This doesn't mean our proof isn't convenient enough — in fact, most purely real-integer proofs of this theorem also rely on this same lemma.

That said, if we grant Wilson's theorem, we can give a quick proof of the lemma (though Wilson's theorem itself is proved using the idea of the prime field). We can show that, for $p=4k+1$,

$$p\left|\left(\frac{p-1}{2}!\right)^2+1\right.$$

By Wilson's theorem, for any prime $p$ we have $(p-1)!+1\equiv 0(\bmod\,p)$. Noting that $mn\equiv (p-m)(p-n)(\bmod\,p)$, it follows that if $p-1$ is a multiple of 4, we can split $1\times 2\times \dots\times(p-2)\times(p-1)$ into two halves: pairing up terms within the first half and multiplying them, and similarly pairing up terms within the second half — the second half then turns out to be congruent to the first half, i.e.

$$\begin{aligned}&(p-1)!=1\times 2\times \dots\times\left(\frac{p-3}{2}\right)\left(\frac{p-1}{2}\right)\left(p-\frac{p-1}{2}\right)\left(p-\frac{p-3}{2}\right)\dots(p-2)(p-1)\\ &(p-1)(p-2)\equiv 1\times 2(\bmod\,p)\\ &(p-3)(p-4)\equiv 3\times 4(\bmod\,p)\\ &\dots\\ &\left(p-\frac{p-3}{2}\right)\left(p-\frac{p-1}{2}\right)=\left(\frac{p-3}{2}\right)\left(\frac{p-1}{2} \right)(\bmod\,p)\end{aligned}$$

So the product of the first half modulo $p$ equals the product of the second half modulo $p$ (when p = 4k+1), and therefore

$$(p-1)!+1\equiv\left(\frac{p-1}{2}!\right)^2+1(\bmod\,p)$$

which gives us exactly the formula we wanted to prove.