Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search