Proof that any square is of the form $3k$ or $3k+1$

Question

Prove that the square of every natural number is of the form $3k$ or $3k+1$, where $k \in \mathbb{Z}$.

I'm trying to reach a contradiction by assuming $n^2 = 3k+2$. Any ideas?

Answer 1

Go for a direct proof. Any natural number is one of the forms: $3m, 3m+1, 3m+2$ where $m$ is a natural number. What do you get when you take the squares of these forms?

Answer 2

Well, you know that any integer can be written in the form $3k$, $3k + 1$ or $3k + 2$ following the division algorithm.

Now let's take the square of each of them;

$(3k)^2 = 9k^2 = 3(3k^2)$, of the form $3k$;

$(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$, of the form $3k + 1$;

$(3k+2)^2 = 9k^2 + 12k + 4 = 9k^2 + 12k + 3 + 1 = 3(3k^2+4k+1)+1$, of the form $3k + 1$;

therefore no integer $n^2$ can be written in the form $3k + 2$, hence all integers squared are of the form $3k$, or $3k + 1$.

Answer 3

Hint mod 3: $n \equiv 0, \pm 1 \implies n^2 \equiv 0, 1$