$a^2 + b^2$ never leaves remainder $3$ when divided by $4$ Already did something like that to prove the square of an even number Always leaves remainder $1$ when divided by $8$, in which I used induction to arrive at the result.
However, I don't know how to use induction to suppose that it does not leave a remainder $3$, and then prove it.
Could somebody help me?
 A: Some simple problems are just too much fun to pass up!
Lauds to lab bhattacharee for presenting the more or less standard approach, which essentially stands on the homomorphism $\pi: \Bbb Z \to \Bbb Z/4 \Bbb Z$ mapping any $n \in \Bbb Z$ to the coset $\bar n = n + 4\Bbb Z$.  Of course the technique works by virtue of the fact the $\pi$ preserves sums and products, and the fact that $c^2 = 0, 1$ for $c \in \Bbb Z/4\Bbb Z$.
Here's the way I used to solve these things back in junior high school, before I knew much about commutative rings, homomorphisms, $\Bbb Z / n\Bbb Z$ and the like:
Three cases:
$a, b \; \text{both even}; \tag{1}$
$a, \; \text{even}, \; b \; \text{odd}; \tag{2}$
$a, b \; \text{both odd}; \tag{3}$
of course (2) covers the case $a$ odd, $b$ even as well.  Then for (1) we write
$a = 2n, b = 2m; \; m, n \in \Bbb Z, \tag{4}$
whence
$a^2 = 4n^2, b^2 = 4m^2, \tag{5}$
whence
$a^2 + b^2 = 4(n^2 + m^2); \tag{6}$
in case (2):
$a = 2n + 1, b = 2m, \tag{7}$
whence
$a^2 = 4n^2 + 4n + 1, b = 4m^2, \tag{8}$
whence
$a^2 + b^2 = 4(n^2 + m^2 + n) + 1; \tag{9}$
case (3):
$a = 2n + 1, b = 2m + 1, \tag{10}$
whence
$a^2 = 4n^2 + 4n + 1, b^2 = 4m^2 + 4m + 1, \tag{11}$
whence
$a^2 + b^2 = 4(n^2 + m^2 + n + m) + 2; \tag{12}$
we thus see that the remainders upon dividing $a^2 + b^2$ by $4$ must always lie in the set $\{0, 1, 2 \}$.  QED!!!
Now that is what I call truly elementary number theory!
A: HINT:
As integer $c\equiv0,1,2,3\pmod 4;c^2\equiv0,1$
So what are possible values of $a^2+b^2\pmod4$ where $a,b$  are any integers?
