Quadratic Residues and Sums of SquaresDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/