# The square of every integer is of the form either $3k+1$ or $3k$

How can I prove that square of every integer is of the form either $3k+1$ or $3k$, but not $3k+2$?

### My approach

I considered first, the integer $n$ to be even and then $n= 2m$; and if $n$ is odd then $n=2m+1$ but this step takes me to nowhere. I get usually stuck in these kind of questions. and this time I seriously need help . So, please post answer in detail and also mention how and why you arrived at that particular step. Thanks in advance.

-
I did not see you take the square of the integers you made. – Raskolnikov Jul 24 '12 at 7:01
Take $n=3k$ or $n=3k\pm 1$ – Kns Jul 24 '12 at 7:05
Nearly the same: math.stackexchange.com/questions/172535/… – Zander Jul 24 '12 at 14:31

HINT: Instead of looking at $n = 2m$ or $n = 2m+1$, look at $n = 3m$ or $n = 3m \pm 1$.
So you mean, that the quadratic residue $x^2 \neq 2 \bmod 3$: $$(3m\pm 1)^2=9m^2\pm6m+1=3m'+1 =1 \bmod 3 \neq 2 \bmod 3$$ $(3m)^2$ is obvious...
Assume $n=3q+r$, $r={0,1,2}$ as per Euclid's lemma. Then $n^2=(3q+r)^2$ $$n^2=(3q)^2+ 2.3q.r +r^2$$ $$n^2=3(3q^2)+3.(2q.r)+r^2$$ $$n^2=3(3q^2+2qr)+r^2$$ $$n^2=3m+r^2,m \in Z$$. If $r=0$ then $n^2=3m+0$, If $r=1$ then $n^2=3m+1$ and if $r=2$ then $n^2=3m+2^2$ i.e., $n^2=3m+3+1$. Therefore $n^2=3m+1$ and never $n^2=3n+2$. Q.E.D.