prove that $n^2 \bmod 4 = 0$ or $1$ for all integers

$\begingroup$

(Use the fact that every integer is either even or odd to prove that $n^2 \bmod 4 = 0$ or $1$ for all integers)

Let $n \in \mathbb{Z}$, then $n$ is either even or odd.

Case 1: ($n$ is odd):By definition of odd $n = 2j + 1$ with $j \in \mathbb{Z}$, then $(2j + 1)^2 = (4j^2 + 4j + 1)$

By definition of mod $4j^2 + 4j + 1 = 4q + r$

$\forall q, r \in \mathbb{Z}$ and $0 \le r \le q$

$4(j^2 + j) + 1 = 4q + r$

$4(j^2 + j) - 4q = -1 + r$

$4(j^2 + j - q) = -1 + r$

Let $s \in \mathbb{Z}$ with $s = j^2 + j - q$, then

$4s = -1 + r$

So by definition of divisibility $4$ divides $n^2$ with a remainder of $1$

I have a feeling I got this wrong and I just bulled my way to get an answer. But I wasn't given any marks here:

case 2: ($n$ is even):

I got this section wrong.

Can someone help solve me this proof that was on my test?

$\endgroup$ 3

2 Answers

$\begingroup$

If $n$ is even $\implies n=2k\implies n^2=(2k)^2=4k^2\equiv 0 \pmod 4$.

If $n$ is odd $\implies n=2k+1\implies n^2=4k^2+4k+1=4(k^2+k)+1\equiv 1 \pmod 4$

$\endgroup$ 4 $\begingroup$

If $n$ is even then $n=2m$, and $(2m)^2=4m^2\equiv 0\pmod{4}$.

$\endgroup$ 2