prime numbers

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