prime numbers

[hughes@ah.com (Eric Hughes)]

> I'm just wondering if anyone knows whether or not (1+4k) can be 
>written as the sum of squares or not, and if so, what the proof 
>of that is? 

[primes, that is]

There's a nice proof in Chapter 15 of Hardy & Wright.  (Need I say the
title?  _An Introduction to the Theory of Numbers_, still one of the
best introductory number theory books around.)

The basic reason is that -1 is always a quadratic residue for a prime
1 mod 4.  (You can simply calculate this with quadratic reciprocity.)
Therefore \exists x: p | ( x^2 + 1 ).  This yields an existence after
looking at primes in the ring Z[i], the Gaussian integers.

If you really want to know more, go buy a copy of the book.  It's well
worth it.

Eric