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 ${p \equiv 1 \bmod 4}$ 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 ${p=4k+1}$ be a prime. Consider the finite set ${S = \{ (x,y,z) \mid x^{2} + 4yz = p \} }$ where ${x,y,z}$ are natural numbers. This set has two involutions: the obvious ${f}$ that sends ${(x,y,z)}$ to ${(x,z,y)}$ and the following: ${g}$ that sends ${(x,y,z)}$ to:

1. ${(x+2z,z,y-x-z)}$, if ${x < y-z}$;
2. ${(2y-x,y,x-y+z)}$, if ${y-z < x < 2y}$;
3. ${(x-2y,x-y+z,y)}$, if ${x>2y}$.

Any fixed point of ${f}$ is of the form ${(x,y,y)}$ and yields a representation of ${p}$ as a sum of two squares:

$\displaystyle x^{2} + 4y^{2} = p.$

The mapping ${g}$ has one fixed point ${(1,1,k)}$. This shows that ${S}$ has odd cardinality; therefore, ${f}$ must have a fixed point. $\Box$

Magic.

Open Problems

Have a happy St. Patrick’s Day.

March 17, 2009 11:47 am

Thank you for sharing this. I notice you did not call it a “proof from the Book”, which is what I would have first thought of.

March 17, 2009 4:13 pm

Do you really think its from the “book”? I not sure myself. I think it is definitely a very neat proof.

March 20, 2009 3:22 pm

Thanks for this post! I had a great time checking all the claims. Now I just need to go read Heath-Brown’s paper, the only reference of Zaiger’s, and see if I can understand where the involution, g, came from.

March 20, 2009 4:05 pm

Love you “hat”? Glad you enjoyed the post….

rjlipton