Thread: sum of squares and congruence problem

1. sum of squares and congruence problem

I searched around and couldn't find anything like this, so here's my questions:

Show that if an integer x is the sum of two squares, then $x \not\equiv 3 mod 4$

proof:
$x = a^2 + b^2$ for a,b integers

Assume $x \equiv 3 mod 4$. (going for a contradiction here)
$a^2+b^2 \equiv 3 mod 4$ -subsitution
$4 | (a^2+b^2-3)$ -def. of congruence
$a^2+b^2-3 = 4k$ for some k int - def. of divides

So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

Thanks

2. $a=2m, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2)$

$a=2m, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+n)+1$

$a=2m+1, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2+m)+1$

$a=2m+1, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+m+n)+2$

3. Originally Posted by Th3sandm4n
I searched around and couldn't find anything like this, so here's my questions:

Show that if an integer x is the sum of two squares, then $x \not\equiv 3 mod 4$

proof:
$x = a^2 + b^2$ for a,b integers

Assume $x \equiv 3 mod 4$. (going for a contradiction here)
$a^2+b^2 \equiv 3 mod 4$ -subsitution
$4 | (a^2+b^2-3)$ -def. of congruence
$a^2+b^2-3 = 4k$ for some k int - def. of divides

So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

Thanks
Depending on whether $a$ is even or odd we get $a^2\equiv 0,1(\bmod 4)$.
Thus, $b^2\equiv 0,1(\bmod 4)$ which means $x = a^2+b^2 \equiv 0,1,2(\bmod 4)$. Thus, $x\not \equiv 3(\bmod 4)$.

4. Thanks, I was just thinking about that on the bus ride back home