Sum of Two Squares

I know that I haven't had a post about math or anything math related for a while, so I think it is time to change this.

Well the problem discussed here really isn't that difficult but it is interesting enough to mention. "Given an integer determine if can be written as the sum of two squares." For example if , however, if instead we had it can be shown that it is not possible to have where .

Sure you could try using "brute force" to solve this but that is boring and definitely not worthy of its own post. The necessary key insight is a theorem by Fermat. The theorem states that a prime number can be expressed as the sum of two squares if and only if . The proof of one direction is not that difficult but a proof of the other direction (that if then is the sum of two squares) requires a little more work. I don't feel like posting them here but feel free to look on Wikipedia, where you will find numerous proofs. The proof by Euler is quite straight forward but is quite long and split into many sections (your call on whether this is a good thing or not). My personal favorite is the first proof by Dedekind using Gaussian Integers.

Now another important fact to know is the following. If two integers, and , can each be written as the sum of two squares, then their product, can be written as the sum of two squares. The proof is just a basic exercise in equation manipulation, if you have not proven this fact for yourself I suggest you try to in your spare time.

Using these two facts the problem basically boils down to "factor ." Actually our task is even easier than this, we only need to find the prime factors, , of such that . Thus if factors as and for some , we have that and is odd, then can not be expressed as the sum of two squares.

Pretty simple, now writing a program to actually do all of these things is a little harder but not by that much.