Patrick Stevens bio photo

Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

Email Twitter Github Stackoverflow

Wherein I detail the most beautiful proof of a theorem I’ve ever seen, in a bite-size form suitable for an Anki deck. I attach the Anki deck, which contains the bulleted lines of this post as flashcards.

Statement

There’s no particularly nice way to motivate this in this context, I’m afraid, so we’ll just dive in. I have found this method extremely hard to motivate - a few of the steps are a glorious magic.

  • is a sum of two squares iff in the prime factorisation of , primes 3 mod 4 appear only to even powers.

Proof

We’re going to need a few background results.

Background

Additionally, we’ll call a number which is the sum of two squares a nice number.

First implication: if primes 3 mod 4 appear only to even powers…

We prove the result first for the primes, and will then show that niceness is preserved on taking products.

  • Let . Then is trivially the sum of two squares: it is .
  • Let be 1 mod 4.
  • Then modulo , we have is square.
  • That is, there is such that .
  • That is, there is such that .
  • divides , but it does not divide either of the two multiplicands (since it does not divide their imaginary parts).
  • Therefore is not prime in the complex integers.
  • Since is a UFD, is not irreducible in the complex integers.
  • Hence there exist non-invertible such that .
  • Taking norms, .
  • Since the norm is multiplicative, .
  • , so .
  • Neither nor was invertible, so neither of them has norm 1 (since in , having norm 1 is equivalent to being invertible).
  • Hence wlog is exactly , since the product of two numbers being means either one of them is 1 or they are both .
  • Let . Then , which was what we needed.

Next, we need to take care of this “even powers” business:

  • is a sum of two squares if is 3 mod 4: indeed, it is .

All we now need is for niceness to be preserved under multiplication. (Recall denotes the conjugate of .)

  • Let be the sum of two squares each, and .
  • Then , and similarly for .
  • Then .
  • So , where .
  • Hence , so is a sum of two squares (since norms are precisely sums of two squares).

Together, this is enough to prove the first direction of the theorem.

Second implication: if is the sum of two squares…

We’ll suppose that has a prime factor which is 3 mod 4, and show that it divides both and .

  • Let have prime factor which is 3 mod 4.
  • Then taken mod , we have .
  • That is, .
  • If is not zero mod , it is invertible.
  • That is, .
  • This contradicts that is 3 mod 4 (since is not square mod ). So is divisible by .
  • Symmetrically, is divisible by .
  • Hence divides , so we can divide through by it and repeat inductively.

That ends the proof. Its beauty lies in the way it regards sums of two squares as norms of complex integers, and dances into and out of , and where necessary.