Happy St Patrick’s Day and Sum of Squares
A short proof of the sum of two square theorem
Neil L. is not a computer scientist–he is a Leprechaun. Since this Tuesday is St. Patrick’s Day it seems right to talk about him. As long as you look at him he cannot escape, but the moment you look away, he vanishes. I thought in the same spirit I would share a wonderfully simple proof that I read recently, it is due to Zaiger. The proof is based on a trick that reminded me a bit of Neil: when you read the proof carefully it clearly works, but if you look away it seems magical.
Theorem 1 Every prime is the sum of two squares.
There are many proofs of this theorem, but the following is definitely very cool. It is based on a simple, but powerful parity principle.
Proof: Let be a prime. Consider the finite set where are natural numbers. This set has two involutions: the obvious that sends to and the following: that sends to:
- , if ;
- , if ;
- , if .
Any fixed point of is of the form and yields a representation of as a sum of two squares:
The mapping has one fixed point . This shows that has odd cardinality; therefore, must have a fixed point.
Have a happy St. Patrick’s Day.