[12524] in Cypherpunks
prime numbers
daemon@ATHENA.MIT.EDU (Eric Hughes)
Wed Apr 27 00:10:24 1994
Date: Tue, 26 Apr 94 21:03:03 -0700
From: hughes@ah.com (Eric Hughes)
To: cypherpunks@toad.com
In-Reply-To: Carrie A. Johnson's message of Tue, 26 Apr 1994 18:31:40 -0500 (CDT) <9404262331.AA13940@chem.udallas.edu>
> 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
