From: hughes@ah.com (Eric Hughes)
Date: Tue, 26 Apr 94 21:07:56 PDT
To: cypherpunks@toad.com
Subject: prime numbers
In-Reply-To: <9404262331.AA13940@chem.udallas.edu>
Message-ID: <9404270403.AA16974@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


> 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