$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?

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!
