n congruent 3 mod 4

Abelian_Math

Prove that if n (mod 4), then n cannot be represented as a sum of two squares.

AUMathTutor

Well, assume a^2 + b^2 = 3 (mod 4).

Then a^2 + b^2 is odd, which means exactly one of a, b is odd. We can call a odd, without loss of generality. b is therefore even.

Clearly, b^2 = 0 (mod 4). The square of any even number is 0 mod 4.

Therefore, a^2 must be 3 mod 4. Ergo

a^2 = 3 (mod 4)
<=>
a^2 = 4n + 3

Any odd number can be written as either 4m+1 or 4m-1. So

(4m+1)^2 = 16m^2 + 8m + 1 = 4n + 3
<=>
16m^2 + 8m = 4n + 2
<=>
8m^2 + 4m = 2n + 1
<=>
4(2m^2 + m) = 2n + 1

A clear contradiction. Checking the other case,

(4m-1)^2 = 16m^2 - 8m + 1 = 4n + 3
<=>
16m^2 - 8m = 4n + 2
<=>
8m^2 - 4m = 2n + 1
<=>
4(2m^2 - m) = 2n + 1

Also a clear contradiction. Therefore, it cannot possible be true that

a^2 = 4n + 3

So it follows that it is not the case that

a^2 = 3 (mod 4)

From which one can deduce that, since b^2 = 0 (mod 4),

a^2 + b^2 = 3 (mod 4)

Cannot happen.

It may not be the prettiest proof, but I'm sure the other regulars will swoop in with a two-liner and make me look like a muppet. ;D

CRGreathouse

Squares are zero or one mod 4.
Thus the sum of two squares cannot be 3 mod 4.

AUMathTutor

"Squares are zero or one mod 4."

I think that taking this statement for granted is sort of presupposing the conclusion. Although a simple proof of this would certainly prove the guy's thing.

I think one should be careful when proving theorems as an exercise... although there may be a theorem which makes your exercise trivial, you're not always allowed to use it per se. For instance, I could ask you to prove that there are infinitely many primes, and you could say "It has been proven that there are infinitely many primes already. Therefore, there are infinitely many primes. QED". Yes, alright. But that's sort of defeating the purpose.

MLeszega

Can you show that n cannot be congruent to 3 (mod 4) by showing that it must be congruent to 0, 1 or 2 (mod 4)? Because you can do this by breaking it down into 3 cases. If n = x^2 + y^2 then either x and y are (1) both even, (2) both odd, or (3) one odd, one even.
For (1) x^2 and y^2 are both congruent to 0 (mod 4) (because they are even), so x^2 + y^2 is congruent to 0 (mod 4).
For (2) x^2 and y^2 are both congruent to 1 (mod 4) (because they are both odd), so x^2 + y^2 is congruent to 2 (mod 4).
Finally, (3) one is odd, the other even. You find that this is congruent to 1 (mod 4).

So then n cannot be congruent to 3 (mod 4) because by our 3 cases it must be either 0,1 or 2 (mod 4).

Sorry in advance if I was unclear or made any other mistakes.

CRGreathouse

If you prefer the 'long' two-line version:
0^2 = 0, 1^2 = 1, 2^2 = 0, 3^4 = 1 (mod 4). Thus squares are 0 or 1 mod 4.
0+0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 2. Thus sums of squares are never 3 mod 4.

AUMathTutor

I suppose that does work, too. Interestingly enough it is exactly what I did, except that I didn't realize that you only had to show it for 0, 1, 2, and 3. You're right, of course.

CRGreathouse

It is the same, you're right. Yours might even be more understandable. I claim only that mine is shorter. :)