Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.
Let n = x^2 + y^2
Assume, aiming for a contradiction, that n is congruent to 3 mod 4.
So, x^2 + y^2 is congruent to 3 mod 4
This implies that 4 | x^2 + y^2 -3
I'm trying to get a contradiction, but I'm stuck here...
Any advice... Thanks..
So you know that if a=n (mod 4), that a^2=n^2 (mod 4), right? So, if you want to know what the square is, mod 4, all you need to know is what the original number is, mod 4. So do that--check all four possibilities. Then, see what you can get by adding any two squares.
In order for n = x^2 + y^2 = 3 (mod 4) it must be that x^2 is even and y^2 is odd, or vice versa (since any number congruent to 3 mod 4 is necessarily odd). Say x^2 is even, so y^2 has to be odd. Then x must be even and y must be odd. So, x = 0 or 2 (mod 4) and y = 1 or 3 (mod 4). Then either way x^2 = 0 (mod 4) and y^2 = 1 (mod 4), so x^2 + y^2 = 1 (mod 4), contradicting the initial hypothesis.
this is basically what Tinyboss said, just thought I'd help spell it out a bit more.