Primes That Are the Sum of 2 Squares

Date: 09/17/1999 at 11:07:53
From: Blake Jennelle
Subject: Proof - primes as the sum of squares

I am unable to prove that every prime of the form 4m + 1 can be 
expressed as a sum of two squares. Can you offer any assistance?

Date: 09/18/1999 at 07:43:55
From: Doctor Floor
Subject: Re: Proof - primes as the sum of squares

Hi, Blake,

Thanks for your question.

We have to prove that if a prime number p == 1 (mod 4), then it can be 
written as the sum of two squares.

Let's assume that p > 5, or consequently that p >= 13. We can do this 
because we know that 5 = 1^2 + 2^2. 

Because p == 1 (mod 4), -1 is a quadratic residue modulo p. And thus 
there is a number x such that x^2 == -1 (mod p). We fix this x. I 
assume you know this fact. If not, ask us for more explanation.

Now consider the set of t such that:

   1. t == ax (mod p) for a = 0, 1 , ..., N; where N = floor(sqrt(p))
   2. 0 <= t <= p-1

Here floor(n) is the integer part of n. So for example, floor(2.9) = 
2,  floor(pi) = 3 and floor(sqrt(2)) = 1.

Then there are N+1 elements of this set. So if we divide the interval 
[0,p-1], in which all elements of the set are found, into N parts, 
there must be one of the parts that contains two elements. And those 
elements must be less than (p-1)/N, the length of the interval, apart.

So we can find two numbers a < b < N, represented in the above set by 
v, w in [0,pi-1] such that v == ax (mod p) and w == bx (mod p), and 
the following holds:

     distance(v,w) < (p-1)/N < (p-1)/(sqrt(p)-1) = sqrt(p) + 1  ...[1]

Let c = b-a. Since a,b < N we have that 0 < c < sqrt(p). And in the 
residue class cx (mod p) there must be an element d in the interval 
[-sqrt(p)-1,sqrt(p)+1] because of [1].

We find:

     c^2 + d^2 == c^2 + (cx)^2 == c^2(1+x^2) == 0 (mod p)

     The last step follows from x^2 == -1 (mod p).

So c^2 + d^2 is divisible by p. But we have also found that

     |c| < sqrt(p) and |d| < sqrt(p) + 1

So c^2 + d^2 < p + p + 2sqrt(p) + 1 < 3p (since p >= 13)

So either c^2 + d^2 = p, and we are done, or c^2 + d^2 = 2p.

But, if c^2 + d^2 = 2p, then c and d are both odd or both even, and we 
find that

     ((c-d)/2)^2 + ((c+d)/2)^2 = (c^2+d^2)/2 = p

does the job.

And the theorem, first stated by Fermat, is proven.

If you need more help, just write us back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/