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

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?

• Do you know induction?
– Cass
Apr 1 '14 at 20:45
• Better to verify it for $n=0,1,2$ and then do three inductions, going from $n$ to $n+3$ in each. Apr 1 '14 at 20:46

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?

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

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