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

### 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/
```
Associated Topics:
College Number Theory
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