20100128, 10:19  #1 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Sum of two squares: Peculiar property
Yesterday, I had some fun with WIMS online calculator on decomposing any positive integer N
into sum of two squares. On playing with it, I found that, as it says A positive integer cannot be a sum of two squares if it has a prime factor of the form 3 (mod 4) to an odd power. Why? I would like to see a proof for it! Since any square will be of the form 0 or 1 (mod 4) only, it is directly quite obvious that sum of two squares cannot be 3 (mod 4). A square can only be 0, 1, 4 or 9 (mod 16). But even if it is the product of two distinct primes of the form 3 (mod 4), or something else multiplied with it, that make the product equal to 1 (mod 4), still is it not possible at all, to be a sum of two squares? How come? :surprised Any proof that is being available anywhere for this case only? Further, that decomposition into two squares has many more surprising properties. 1) If N is the product of n distinct primes of the form 1 (mod 4), then the number of ways that N can be written as sum of two squares is 2^{n1}. Show how! 2) If N has even one single prime factor of form 3 (mod 4) to an odd power, then decomposing N as sum of two squares is impossible! 3) If p is a prime of the form 1 (mod 4), then the number of ways that p^{n} can be written up as sum of two squares is given by Int((n/2)+1). Again why? 4) A number multiplied with a power of 2, does not change the number of ways of decomposing that number into sum of two squares at all! 5) Further, how to determine the number of ways of decomposing into sum of two squares for some complex expressions of the form p_{1}^{2}*p_{2} or p_{1}^{9}*p_{2}^{7}*p_{3}, etc. where the p_{i}'s are distinct prime numbers of the form 1 (mod 4) only? This is rather looking up to be somewhat tedious only... Last fiddled with by Raman on 20100128 at 10:20 
20100128, 15:26  #2  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
I'm going to take a small stab at this but I will botch it because I don't swim with the big fish.
In binary, it is helpful to notice that odd numbers squared are not only of the form 1 (mod) 4, they are are more specifically of the form 1 (mod) 8. In a binary representation that means they always ends in 001. This is because: (2n+1)^{2} = = 4n^{2} + 4n + 1 = 4(n^{2} + n) + 1 If n itself is also odd, n^{2} + n will be even (odd number + odd number equals even number) so another 2 can be factored out making the total result of the odd number squared = 8k + 1. This is the form 1 (mod) 8. (k = (n^{2 } + n)/2) An even number will always have a 0 bit less significant than the least significant 1 bit. These number of these least significant 0s will be doubled after squaring (as they do in any integer base i.e. 10 * 10 = 100 etc.) The binary representation of squaring the bits starting from the least significant 1 bit will be exactly like any odd number squared (except for the magnitude/position as changed by doubling the number of 0s to the right of it) Quote:
So if I have made this at all clear, adding squares can be directly thought of as selecting patterns ending in either 00 or 001 and adding a combination of them together.. Quote:
That is, the sum of two squares will only be values that can be attained by adding selections ending in 00 or 001 together) Quote:
I'm stopping here because the rest doesn't come so easily to me and I think I have already bitten off more than I can chew Last fiddled with by only_human on 20100128 at 15:33 Reason: changes a factor mistake from 2 to 4 

20100129, 07:27  #3  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
Thank you, everyone, for the mercy of not replying directly to my message but I don't want to derail the thread so feel free to answer the puzzle. I, myself am still thinking about the puzzles numbered section and may join in again on that aspect. 

20100129, 11:00  #4  
"William"
May 2003
New Haven
2^{2}×593 Posts 
Quote:
(a^{2} + b^{2}) * (x^{2} + y^{2}) = (ax+by)^{2} + (aybx)^{2} This pretty little formula has a simple generalization for numbers of the form a^{2}+nb^{2} (n fixed; n=1 above) 

20100129, 15:17  #5  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
10011101001_{2} Posts 
It is quite puzzling that every prime number of the form 1 (mod 4) has
UNIQUE representation as sum of two squares, while every prime number of the form 3 (mod 4) has no such representation. This is obvious though, as I had only mentioned up above already. Quote:
If all prime factors are of the form 1 (mod 4), then product is 1 (mod 4) If the product is 3 (mod 4), it quite obviously has no decomposition into two squares. In order to make the product equal to 1 (mod 4), there should be even number of primes of the form 3 (mod 4), atleast one of them much be distinct from the others, such that it has no decomposition into two squares, as by the rule saying. A square can be only 0,1,4,9 (mod 16) or 0,1,4 (mod 8) Trying to prove that fact: If all primes are of form 1 (mod 16), then the product is 1 (mod 16) If there are two distinct primes of the form 3 (mod 4), then the product is 9 (mod 16), no there can be a prime of the form 9 (mod 16), or more primes of the form 3 (mod 4), and then the product can be 1 (mod 16) as well. There can be primes of the form 9 (mod 16) as well, that are of the form 1 (mod 4). With these primes, with primes of form 1 (mod 16), the product can be 1 (mod 16) or 9 (mod 16) as well. With these, with primes of form 5 (mod 16) and then 13 (mod 16), the product can be either 1 (mod 16), 5 (mod 16), 9 (mod 16), or 13 (mod 16). Each has its own way of splitting up into sum of two squares. If N is 1 (mod 16), it can be sum of two squares of form 0 (mod 16) & 1 (mod 16) If N is 9 (mod 16), it can be sum of two squares of form 0 (mod 16) & 9 (mod 16) If N is 5 (mod 16), it can be sum of two squares of form 4 (mod 16) & 1 (mod 16) If N is 13 (mod 16), it can be sum of two squares of form 4 (mod 16) & 9 (mod 16) as well. Sum of two squares can be only 0,1,2,4,5,8,9,10,13 (mod 16). But even then, it covers up all sums of the form 1 (mod 4). The fact to be proved is that: If a number of the form 1 (mod 4) has some decomposition into sum of two squares, then it has no prime factors of the form 3 (mod 4) to an odd power at all. How to approach it up? Last fiddled with by Raman on 20100129 at 15:19 

20100202, 20:59  #6 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
2351_{8} Posts 
Got up the proofs from one of the books within library only...
1) It is obvious that a square can be only 0 or 1 (mod 4). So, sum of two squares cannot be 3 (mod 4). 2) Next, the proof that if p divides N, and p is prime of form 3 (mod 4) then N has no sum of two squares representation in lowest terms. That is, N cannot be represented as x^{2}+y^{2}, such that gcd(x,y) = 1. Proof: Since pN, so px^{2}+y^{2}. If px, then py also, so gcd(x,y) is not 1. So, p cannot divide x or y. So, x and y are congruent between 1 and p1 (mod p). Let y=ux, where 1 <= u <= p1. Then, since N = x^{2}+y^{2} = 0 (mod p), x^{2}(1+u^{2}) = 0 (mod p). p does not divide x, so (1+u^{2}) = 0 (mod p). So, 1 is a quadratic residue (mod p). This is false when p is a prime of form 3 (mod 4). So, N has no sum of two squares representation in lowest terms (x,y) = 1. If it exists, it should be such that y = ux (mod p) such that u^{2} = 1 (mod p), where p is a prime of form 3 (mod 4) only. 3) Next the proof that if N has a prime factor p of form 3 (mod 4) to an odd power, then N has no sum of two squares representation at all. Let p^{c} divide N, and p^{c+1} does not divide N, where c is odd, let N = x^{2}+y^{2} with gcd(x,y) = d. then N = d^{2}(X^{2}+Y^{2}) with gcd(X,Y)=1. Putting X^{2}+Y^{2} = n, N = d^{2}n. Let p^{m} be the highest power of p, that divides d. Since n = N/d^{2}, so highest power of p that divides n is c2m. Since c is odd, c2m > 0. So, p divides n. Since, n = X^{2}+Y^{2}, with gcd(X,Y) = 1, p dividing N with p being a prime of form 1 (mod 4). This is not possible by (2). Hence the result. Even if N contains power of p to an even power, the representation of N as sum of two squares can be only multiples of those values of N divided by all those primes that are congruent to 3 (mod 4). 4) If p is a prime of form 1 (mod 4), then there exist values of x,y less than p such that x^{2}+y^{2} = mp, where 0 < m < p. Proof: If p is prime of form 1 (mod 4), then 1 is a quadratic residue (mod p). If z is quadratic residue, then so is z. Since z^{2} is quadratic residue, so is z^{2}. Since k^{2} mod p = (pk)^{2} mod p, the quadratic residues are symmetric, so the distinct quadratic residues are from k^{2}, where k is between 1 to (p1)/2 only. Within this range, for some quadratic residue x^{2}, there exist some other value of y such that y^{2} = x^{2} mod p. So, x^{2}+y^{2} = 0 (mod p). Let x^{2} + y^{2} = mp. Clearly, m>0. Since, x^{2} + y^{2} <= 2*((p1)/2)^{2}, so m<p. 5) Next comes the proof that for any prime p of form 1 (mod 4), there exist values of x,y such that x^{2}+y^{2} = p. Proof by method of infinite descent. If m=1, then there is nothing to prove at all. If m>1, then x^{2}+y^{2} = mp, so that x^{2}+y^{2} = 0 (mod m). Let r and s be minimal residues of x and y (mod m), such that m/2 < r,s < m/2. r is congruent to x (mod m) and y is congruent to s (mod m). So, r^{2}+s^{2} = 0 (mod m). r and s cannot be both zero simultaneously, because if so, then m divides both x and y, so m^{2} divides x^{2}+y^{2} = mp, so m divides p. This is false since p is prime. Let r^{2}+s^{2} = nm. Since, m/2 < r,s < m/2, so n < m. (x^{2}+y^{2})(r^{2}+s^{2}) = m^{2}np (xr+ys)^{2} + (xs  yr)^{2} = m^{2}np Since x and r belong to the same residue class (mod m), and so does y and s, m divides (xr+ys), since x^{2}+y^{2} = 0 (mod m), m also divides (xsyr) = (xyyx) mod m = 0 (mod m). Let (xr+ys) = am, and that (xsyr) = bm, then a^{2}m^{2} + b^{2}m^{2} = m^{2}np or that, a^{2} + b^{2} = np, where n < m. This says that there exist integers a, b such that a^{2}+b^{2} = np, where n<m. We can keep continuing this descent until we get some integers u and v such that u^{2}+v^{2} = p, where p is a prime of form 1 (mod 4). 6) Next we have to prove such representation is unique. Let N = a^{2}+b^{2} = c^{2}+d^{2}, with two distinct sum of two squares representation. Then N is composite. Proof: Since even number other than 2 is composite, we will consider only the case when N is odd. 2 has only one such representation, by the way. If N is odd. One of a,b is odd, and so is c,d pair as well. Let a,c be odd. b,d be even. Let a>c, then b<d. Since we have that a^{2}+b^{2} = c^{2}+d^{2} thus, a^{2}c^{2} = d^{2}b^{2} (ac)(a+c) = (db)(d+b) where ac, a+c, db, d+b are all even. Let gcd(ac,db) = g, where g is clearly even. Let ac = ug, db = vg, where gcd(u,v)=1. Then, ug(a+c) = vg(d+b), u(a+c) = v(d+b). So u divides d+b, v divides a+c. Let a+c = tv. Putting that, then it becomes that d+b = tu. Since that gcd(u,v)=1 and a+c and d+b are both odd, hence that t is being even only. So, 2N = a^{2} + b^{2} + c^{2} + d^{2} 4N = 2a^{2} + 2c^{2} + 2b^{2} + 2d^{2} 4N = (a+c)^{2} + (ac)^{2} + (d+b)^{2} + (db)^{2} 4N = t^{2}v^{2} + u^{2}g^{2} + t^{2}u^{2} + v^{2}g^{2} 4N = (t^{2}+g^{2})(u^{2}+v^{2}) N = ((t/2)^{2}+(g/2)^{2})(u^{2}+v^{2}) Since t and g are both odd, so we have that (t/2) and (g/2) are both integers. So, N is representable as product of two integers, both being clearly > 1 only. Thus, N is composite. EVERY PRIME OF FORM 1 (MOD 4) CAN BE UNIQUELY REPRESENTED AS SUM OF TWO SQUARES. 7) It is also given in the book that every number that is not of form 4^{b}(8c+7) can be represented as sum of three squares. 8) Regarding number of ways of representing an arbitrary value of N as sum of two squares: Since (a^{2}+b^{2})(c^{2}+d^{2}) = (ac+bd)^{2} + (adbc)^{2} = (acbd)^{2} + (ad+bc)^{2} The product of two distinct primes of form 1 (mod 4) can be represented as sum of two squares in two ways. Pending exercise to prove that these are the only ways of such representation. Why is it so? Continuing up in this way, it is certainly possible to see that the product of k distinct primes of form 1 (mod 4) can be represented in 2^{k1} ways. Only that much? Sure about that? 9) Regarding product with a power of 2 will not change the number of ways of representation at all: This is because of the fact that 2(a^{2}+b^{2}) = (a+b)^{2} + (ab)^{2} Continuing this up only, we will get that 4(a^{2}+b^{2}) = (2a)^{2} + (2b)^{2} Are these the only ways of such representation? Sure enough already? Only this much? Last fiddled with by Raman on 20100202 at 21:00 
20100203, 02:53  #7  
"(^r'°:.:)^n;e'e"
Nov 2008
;t:.:;^
2^{3}·5^{3} Posts 
assonance
Quote:
Last fiddled with by cmd on 20100203 at 02:54 Reason: color 

20100209, 09:19  #8  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
One book on my shelf is Harvey Cohn's Advanced Number Theory. On page 2 of the introduction he tells me Quote:
Quote:
Wblip's comment about the generalization intrigued me so I did a little online searching and was a bit surprised at the directions some of it led. First Proofs of Fermat's theorem on sums of two squares [Wikipedia] Quote:
And these steps have skirted an elephant in the room (I presume): Quadratic Reciprocity. That is Chapter 11 in Harvey Cohn's book. This scares me a bit because I feel some would say that all of this would best start there. Last fiddled with by only_human on 20100209 at 09:26 Reason: fix superscripts in quote 

20100209, 18:40  #9  
"William"
May 2003
New Haven
2^{2}×593 Posts 
Quote:
(a^{2}+k*b^{2}) * (x^{2}+k*y^{2})
= (ax+kby)^{2} + k (aybx)^{2} = (axkby)^{2} + k (ay+bx)^{2} 

20100210, 23:31  #10  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
a minor tidbit of a puzzle
Quote:
As one might notice, my approach to mathematics is really more like a survey with wonder but not much real work. In this vein, I noticed something about odd squares that I don't recall ever hearing explicitly mentioned. It doesn't merit a thread or any real work but I present it as a minor tidbit of a puzzle: As I mentioned earlier in the thread, the binary representation of an odd integer squared ends with "001." For the puzzle, we lop this invariant portion off the representation and consider what is left. To avoid quibbles I prefer to skip 1^{2}. In sequence the next would be 3 squared followed by 5 squared... Looking at the binary representations of the squares these are 1001 and 11001... After lopping off the "001" tail these numbers are "1" and "11" in binary. So looking at all of the "trimmed" numbers, what are they often called? 

20100211, 10:19  #11  
Nov 2005
2·7·13 Posts 
Quote:
Quote:
::EDIT:: If you want a proof, consider the property of (n+1)^2n^2 = n^2+2n+1n^2 = 2n+1 Last fiddled with by nibble4bits on 20100211 at 10:23 Reason: Note on how to prove this is always true 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Peculiar activity in the 1M range...  petrw1  PrimeNet  5  20110114 18:01 
Peculiar behaviour of prime numbers .....  spkarra  Math  8  20090720 22:47 
Peculiar Case of Benjamin Button is AWESOME!!!!!!!  jasong  jasong  7  20090101 00:50 
A particularly peculiar problem  fivemack  Puzzles  7  20081114 07:56 
Special property for mod  dsouza123  Math  4  20031031 05:49 