From: spamless@Nil.nil Subject: Re: Primes as sums of squares? Date: 4 May 2000 16:37:18 -0400 Newsgroups: sci.math Summary: [missing] A. Bijanki wrote: > I heard that Fermat proved that any prime of the form 4k+1 is a sum of two > squares. > 5 = 2^2 + 1^2 > 13 = 2^2 + 3^2 > 17 = 4^2 + 1^2 Here is a way of showing that primes of the form 1+4n can be written as a sum of two squares using mostly elementary results. (One can do it more quickly using the fact that Z[i] is a UFD which one can prove since Z[i] is a Euclidean Domain. But I don't want to mention the word "ideal" in proving that Euclidean domains are UFDs. One can use rather elementary results to show that Z[i] is a UFD without mentioning Euclidean Domains or ideals - but it is a bit more work - but you see more methods. I don't think that the shortest proofs are always the nicest or most instructive.) [Z[i]: the ring of INTEGER1+ i*INTEGER2 If a+ib is divisible by c+id in Z[i], it means that the quotient is an integer plus i*another_integer. Z_p : Integers mod p. This is a field. The non-zero terms (numbers not divisible by p) form a commutative group under multiplication. The multiplicative inverse of a mod p (a between 1 and p-1) is found using the (extended) Euclidean algorithm).] | : a|b - a divides b. There exists a c with b=ac. This will either require c to be in Z[i] (integer + i*other_integer) or Z (depending on the context).] Complete details of a rather elementary proof. ============================================== Lemma 1: There are no solutions to x^2=-1 mod p for p=3 mod 4. Proof: Supposing there were. Then x^4=1 mod p. The multiplicative order of x must divide 4. It is not one (since x^1<>1 mod p) nor two (since x^2<>1 mod p) and so is four. The order of any element of a group (in this case the multiplicative group of Z_p, which has p-1 elements) must divide the order of the group. But for p=3 mod 4, p-1 is divisible by 2 but not 4. This is a contradiction (x cannot have order four). Q.E.D. Lemma 2: If p is congruent to 3 mod 4 and divides x^2+y^2 then p divides x and y. Proof: Suppose x^2+y^2=0 mod p (p=3 mod 4). If p divides x, then p divides y^2 and hence y. If p does not divide x, then x has a multiplicative inverse mod p and we have 1+(y*x^-1)^2=0 mod p and y*x^-1 is a solution to X^1=-1 mod p (which is impossible by the prior lemma). Q.E.D. Lemma 3: If p=u^2+v^2 is a prime and divides x^2+y^2 then x+iy is divisible by u+iv or u-iv in Z[i] (note: this includes the case of 2=1^2+1^2) Proof: If p|y, then since p|x^2+y^2, p|x^2 and so p|x and so p|x+iy. Thus p|x+iy if p divides y and in the proof we can now consider just those other cases, where p does not divide y. Consider x^2+y^2=0 mod p and u^2+v^2=p=0 mod p. As y<>0 mod p, it has an inverse so we have: (x/y)^2+1=0 mod p and (u/v)^2+1=0 mod p. As x/y and u/v (in Z_p) are both solutions to the quadratic x^2+1=0 (in Z_p, a field) which has only two roots (say, R and -R) we must have x/y=u/v mod v or x/y=-u/v mod p. NOTE that: (-u/v)(u/v) = -u^2/v^2 = -(-1) = mod p so (u/v)^(-1)=v/u mod p is just -u/v, i.e. v/u=-u/v mod p Case 1: x/y = u/v mod p Then x/y=u/v=-v/u mod p and we have: xv-yu=0 mod p and xu+yv=0 mod p (x+iy)/(u+iv)=(x+iy)(u-iv)/(u^2+v^2)= (xu+yv)/p-i(xv-yu)/p but p divides both xv-yu and xu+yv so these are both integers and this is m+ni (m,n in Z) and so: (x+iy)/(u+iv)=m+ni or u+iv|x+iy in Z[i] Case 2: x/y = -u/v mod p Then x/y=-u/v=v/u mod p and: xv+yu=0 mod p and xu-yv=0 mod p (x+iy)/(u-iv)=(x+iy)(u+iv)/p=(xu-yv)/p+i(xv+yu)/p is in Z[i], so u-iv|x+iy Q.E.D. NOTE: if a+ib|c+id in Z[i] then a^2+b^2|c^2+d^2 in Z and the ratio can be written as the sum of two squares since we have integers m, n with c+id=(a+ib)(m+ni) and taking (complex) conjugates c-id=(a-ib)(m-ni) and multiplying these we get c^2+d^2=(a^2+b^2)(m^2+n^2) and thus: Lemma 4: If x^2+y^2 is divisible by a prime, u^2+v^2 then the ratio, (x^2+y^2)/(u^2+v^2) can be written as the sum of two squares. (NOTE: This includes the case of 2=1^2+1^2) Proof: x+iy is divisible by u+iv or u-iv and the note above. Lemma 5: If p is a prime congruent to 1 mod 4, then there is an x satisfying x^2=-1 mod p (x=[(p-1)/2]! mod p). Proof: Take the numbers not congruent to zero mod p (but take the set of integers from -(p-1)/2 to (p-1)/2 other than zero inclusive instead of the integers from 1 to p-1: e.g. for p=5, take -2,-1,1,2). There are p-1 of them. Let them be x_i (i=1 to p-1). Consider the product of the x_i's. For each x_i another (different x_j) appears as its multiplicative inverse EXCEPT for x_.=1 and -1 (these are the two solutions, since this is a field, at most two, satisfying x^2=1 - that is, where the multiplicative inverse is equal to the number itself). So, multiplying these out, we multiply out numbers times their inverses (giving a bunch of "1"s) and 1*(-1) - so the product of the x_i's is -1 mod p (or (p-1)!+1=0 mod p). But, the product of the x_i's (which is (p-1)! MOD p) is the product of the numbers from -(p-1)/2 to (-1) (that product is (-1)^[(p-1)/2]*((p-1)/2)!) times the product from 1 through (p-1)/2 ((p-1)/2)!) and so we have (-1)^([p-1]/2)*[(p-1)/2]^2=-1 mod p. Thus, if (p-1)/2 is even (p=1 mod 4), x^2=-1 mod p where x=[(p-1)/2]! mod p. ------ Now we can use induction to show that all primes congruent to 1 mod 4 can be written as the sum of two squares (and even have a recursive method to obtain such expansion). Theorem: Every prime congruent to 1 mod 4 can be written as the sum of two squares. Proof: Suppose p is a prime congruent to 1 mod 4 and we know that all primes congruent to 1 mod 4 which are smaller than p CAN be written as the sum of two squares (and also that 2=1^2+1^2) - we wish to show then that p can be written as the sum of two squares (and have a method of obtaining the expansion based on the expansions of the smaller primes). First, find a solution to x^2=-1 mod p, 1 utécie (scripsit): >> Here is a way of showing that primes of the form 1+4n can be written as >> a sum of two squares using mostly elementary results. >> ... >Well, this is quite a piece of work. FAQ material, imo. What do you >think? >-- >M. TIBOUCHI >C:\> ECHO Let's clean up everything... >Let's clean up everything... >C:\> DELTREE C:\WINDOWS\ The original article had disappeared by the time I saw this, and the quoted article doesn't say much about the proof. However, while looking for material on other postings, I discovered the February, 1990 issue of the Monthly (which Monthly? -- *THE* Monthly! -- see .sig). There is an article by Zagier bringing a proof by Heath-Brown to a wider audience, and an "Editor's Corner" piece by Wagon elaborating on the algorithmic aspects of writing numbers as sums of two squares. Wagon shows that the Euclidean algorithm produces a representation of $n$ as a sum of two squares from a solution of $x^2=-1 (n)$. For primes congruent to 1 mod 4, the congruence is easily solved (in practice, but the proof that it is easy requires ERH). Unfortunately, I did not know of Wagon's article when I prepared my report for the New York Number Theory Seminar, which appears in the 1991-1995 publication of the Seminar, published by Springer (ISBN 0-387-94826-0) -- I should have cited his article. My article used this method of representing numbers as sums of two squares to motivate a similar construction for sums of four squares. Moreover, the same method can be used to reduce arbitrary binary quadratic forms (see Mollin: "Quadratics", CRC Press, 1996).