To Show: $4k+3$ can't be written as $a^2+b^2$ I'm studying Introduction to Arithmetic Theory and I see this question:
Show that any number of the form $4k+3$ can't be written as $a^2+b^2$ where $a,b$ are natural numbers.
I don't know how to solve it. Can anyone help me?
 A: If $k\equiv 0\pmod 4$: $k^2\equiv 0\pmod 4$.
If $k\equiv 1\pmod 4$: $k^2\equiv 1\pmod 4$.
If $k\equiv 2\pmod 4$: $k^2\equiv 0\pmod 4$.
If $k\equiv 3\pmod 4$: $k^2\equiv 1\pmod 4$.
So no matter what $a, b$ is modulo $4$, the sum of their squares will be $0, 1$ or $2$ modulo 4, not $3$.
A: $a$ and $b$ cannot be both odd or both even because $a^2+b^2$ would be even and $4k+3$ is odd. So WLOG we can write $a=2m+1$ and $b=2n$ for some integers $m$ and $n$, from where we get $a^2+b^2=4(m^2+m+n^2)+1$ which cannot be of the form $4k+3$
A: Simply consider this question in cases:
Case 1: Suppose a is odd and b is odd, then  a=2m+1 and b=2n+1 for some whole numbers m and n.
$${a^2+b^2=(2m+1)^2 +(2n+1)^2=4(m^2+n^2+m+n)+2=4k+2}$$
Case 2:Suppose a is odd and b is even, then a=2m+1 and b=2n for some whole numbers m and n.
$${a^2+b^2=(2m+1)^2+(2n)^2=4(m^2+n^2+m)+1=4k+1}$$
Case3: Suppose a is even and b is odd, then a=2m and b=2n+1 for some whole numbers m and n.
$${a^2+b^2=(2m)^2+(2n+1)^2=4(m^2+n^2+n)+1=4k+1}$$
Case4: Suppose  a is even and b is even, then a=2m and b=2n for some whole numbers m and n.
$${a^2+b^2=(2m)^2+(2n)^2=4(m^2+n^2)=4k}$$
By analysing all the cases You will get that sum of squares of two natural numbers can be only of the form 4k, 4k+1 or 4k+2.
I know this proof is long and boring but it is easiest to understand.
A: Reduce the equation modulo 4 and then look at the different values $a^2$ and $b^2$ take on. Is it possible that $a^2 + b^2 \equiv 3 \mod 4$?
