Quadratic Residues and Sums of Squares

Date: 10/28/98 at 01:48:21
From:  yeo wee meng
Subject: Number Theory

Dear Dr. Math, 

In one of the lemmas in number theory:

    If p is an odd prime number, then there exist x, y such that 
    x^2 + y^2 +1 = kp  and  0 < k < p.

In one of the sentences it says that if p = 3 (mod 4) (where = is the 
congruent sign), then x^2 = (-a) (mod p). 

Now, (a-1), being positive and less than a, must be a quadratic 
residue modulo p, and so there exists y with 0 < y < (p-1)/2 such that 
y^2 = (a-1)mod p. Why is this so?

My second question is, how does this lemma lead to the proof in showing 
that all prime numbers are expressible as a sum of 4 squares of 
integers? 

Thank you for answering my question.

Date: 10/28/98 at 13:07:03
From: Doctor Rob
Subject: Re: Number Theory

First part:

I assume here that a is the least positive quadratic nonresidue modulo 
p. Since p = 3 (mod 4), -1 is a quadratic nonresidue, so -a = a*(-1), 
being the product of two nonresidues, is a quadratic residue. That is 
why the x exists. Since a was the *least* positive, a-1, being smaller 
and still positive, must be a quadratic residue. That is why y exists. 
The bounds on x and y are derived from these facts. If x is a square 
root of -a, so is p-x, so we can take x to be the smaller one. If y is 
a square root of a-1, so is p-y, so we can take y to be the smaller 
one. Then x < p/2  and y < p/2, and since p is odd, that means 
0 < x <= (p-1)/2 and 0 < y <= (p-1)/2. More than this we cannot 
conclude.

Second part:

You have expressed m*p = x^2 + y^2 + 1^2 + 0^2 as the sum of four 
squares, and 0 < m < p. The next step is to let k be the least positive 
integer that can occur in expressions of the form:

   k*p = x1^2 + x2^2 + x3^2 + x4^2

Clearly 0 < k <= m < p. First one proves that k cannot be even. If k
were even, then 0, 2, or 4 or the xi's would be even. If just two are
even, renumber them so that they are the first two. Then:

   (k/2)*p = 
   ([x1+x2]/2)^2 + ([x1-x2]/2)^2 + ([x3+x4]/2)^2 + ([x3-x4]/2)^2

and all the expressions in parentheses are integers, so k would not be
least. Thus k must be odd. We assume k >= 3. Define numbers yi such
that:
   
   yi = xi (mod k),  -(k-1)/2 <= yi <= (k-1)/2

Then:

   y1^2 + y2^2 + y3^2 + y4^2 = x1^2 + x2^2 + x3^2 + x4^2 (mod k)
                             = 0 (mod k)

and so:

   y1^2 + y2^2 + y3^2 + y4^2 = k*n, 0 <= n <= (1/k)*4*[(k-1)/2]^2 < k

If n = 0, we would have k*p = 0 (mod k^2), so p = 0 (mod k), which is
impossible since k < p and p is prime. Then:

   k^2*n*p = (k*n)*(k*p)
           = (y1^2 + y2^2 + y3^2 + y4^2)*(x1^2 + x2^2 + x3^2 + x4^2)
           = (x1*y1+x2*y2+x3*y3+x4*y4)^2 + (x1*y2-x2*y1+x3*y4-x4*y3)^2 
           + (x1*y3-x3*y1+x2*y4-x4*y2)^2 + (x1*y4-x4*y1+x2*y3-x3*y2)^2
           = a1^2 + a2^2 + a3^2 + a4^2

Now you can show that each of the quantities a1, a2, a3, and a4 in
parentheses in this next-to-last expression are congruent to 
0 modulo k, so we can divide through by k^2 to get:

   n*p = (a1/k)^2 + (a2/k)^2 + (a3/k)^2 + (a4/k)^2

with 0 < n < k. Again, k is not least.

The conclusion is that k = 1 is the least value, and so it is possible 
to write 1*p = p as the sum of four squares.

Note:

This can be made into an algorithm. Consider p = 1633267. Then a = 2 
is the least quadratic nonresidue, and x^2 = -2 has the solutions 
x = 687406 and 945861 (mod p). We pick x = 687406.  
y^2 = 1 has the solutions y = 1 and y = 1633266. We pick y = 1. Then

   687406^2 + 0^2 + 1^2 + 1^2 = 289314*1633267

Dividing by 2, we get:

   343703^2 + 343703^2 + 1^2 + 0^2 = 144657*1633267

Define y1 = 54389, y2 = 54389, y3 = 1, y4 = 0, and then:

   54389^2 + 54389^2 + 1^2 + 0^2 = 40899*144657

Multiplying these together, and using the identity, we find that:

   a1 = 37387324935 = 144657*258455
   a2 =           0 = 144657*     0
   a3 =      289314 = 144657*     2
   a4 =      289314 = 144657*     2

Then:

   40899*1633267 = 258455^2 + 2^2 + 2^2 + 0^2

Repeating this process, y1 = 13061, y2 = 2, y3 = 2, y4 = 0, and then:

   13061^2 + 2^2 + 2^2 + 0^2 = 4171*40899

Multiplying these together, and using the identity, we find that:

   a1 = 3375680763 = 40899*82537
   a2 =     490788 = 40899*   12
   a3 =     490788 = 40899*   12
   a4 =          0 = 40899*    0

Then:

   4171*1633267 = 82537^2 + 12^2 + 12^2 + 0^2

Repeating this process, y1 = -883, y2 = 12, y3 = 12, y4 = 0, and then:

   (-883)^2 + 12^2 + 12^2 + 0^2 = 187*4171

Multiplying these together, and using the identity, we find that:

   a1 = -72879883 = 4171*(-17473)
   a2 =   1001040 = 4171*     240
   a3 =   1001040 = 4171*     240
   a4 =         0 = 4171*       0

Then:

   (-17473)^2 + 240^2 + 240^2 + 0^2 = 187*1633267

Repeating this process, y1 = -82, y2 = 53, y3 = 53, y4 = 0, and then:

   (-82)^2 + 53^2 + 53^2 + 0^2 = 66*187

Multiplying these together, and using the identity, we find that:

   a1 = 1458266 = 187*   7798
   a2 = -906389 = 187*(-4847)
   a3 = -906389 = 187*(-4847)
   a4 =       0 = 187*      0

Then:

   7798^2 + (-4847)^2 + (-4847)^2 + 0^2 = 66*1633267

Dividing by two:

   (7798/2)^2 + (7798/2)^2 + (-9694/2)^2 + (0/2)^2 = 33*1633267
   3899^2 + 3899^2 + (-4847)^2 + 0^2 = 33*16633267

Repeating this process, y1 = 5, y2 = 5, y3 = 4, y4 = 0, and then:

   5^2 + 5^2 + 4^2 + 0^2 = 2*33

Multiplying these together, and using the identity, we find that:

   a1 = 19602 = 33* 594
   a2 =     0 = 33*   0
   a3 = 39831 = 33*1207
   a4 = 39831 = 33*1207

Then:

   1207^2 + 1207^2 + 594^2 + 0^2 = 2*1633267

Dividing by two:

   1207^2 + 297^2 + 297^2 + 0^2 = 1633267

Success!

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/