# 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 $\displaystyle x \not\equiv 3 mod 4$

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

Assume $\displaystyle x \equiv 3 mod 4$. (going for a contradiction here)
$\displaystyle a^2+b^2 \equiv 3 mod 4$ -subsitution
$\displaystyle 4 | (a^2+b^2-3)$ -def. of congruence
$\displaystyle 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. $\displaystyle a=2m, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2)$

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

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

$\displaystyle 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 $\displaystyle x \not\equiv 3 mod 4$

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

Assume $\displaystyle x \equiv 3 mod 4$. (going for a contradiction here)
$\displaystyle a^2+b^2 \equiv 3 mod 4$ -subsitution
$\displaystyle 4 | (a^2+b^2-3)$ -def. of congruence
$\displaystyle 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 $\displaystyle a$ is even or odd we get $\displaystyle a^2\equiv 0,1(\bmod 4)$.
Thus, $\displaystyle b^2\equiv 0,1(\bmod 4)$ which means $\displaystyle x = a^2+b^2 \equiv 0,1,2(\bmod 4)$. Thus, $\displaystyle x\not \equiv 3(\bmod 4)$.

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