1. Modulus Proof

Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

Proof:

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...

2. Originally Posted by jzellt
Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

Proof:

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...

Check what are the squares modulo 4 and show that the sum of any two of them cannot be 3 (mod 4)

Tonio

3. I still don't know how to show this. Can someone please post the proof of this. I need to know how to show this for my exam

4. 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.

5. Originally Posted by jzellt
Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

Proof:

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...