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