Skip to content

Happy St Patrick’s Day and Sum of Squares

March 16, 2009

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


Open Problems

Have a happy St. Patrick’s Day.

8 Comments leave one →
  1. Amit C permalink
    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.

    • rjlipton permalink*
      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.

  2. sumidiot permalink
    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.

  3. rjlipton permalink*
    March 20, 2009 4:05 pm

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


  4. anonymous permalink
    March 22, 2009 8:10 pm

    Actually Chapter 4 of “Proofs from THE BOOK” discusses precisely this problem. They present Heath-Brown’s proof, of which Zagier’s is a condensed version.

  5. Luke G permalink
    April 12, 2009 2:59 pm

    I was a bit suspicious of this proof that it never mentioned the need for p to be prime. This is hidden in the statement that g has only 1 fixed point. Nice proof!


  1. Hardy and Wright, Chapter 2 « Sumidiot’s Blog
  2. Leprechauns Go Universal | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s