Use the Division Algorithm to show the square of any integer is in the form $3k$ or $3k+1$

By the division algorithm, $$x = 3q + r,\text{ where } r \in \{0, 1, 2\}.$$ So express $$x^2 = 9q^2 + r^2 + 6qr = 3(3q^2 + 2qr) + r^2.$$ For a given $x$ if $r = 0$ or $1,$ then we're done. If $r = 2$ then $r^2 = 4 = 3 + 1,$ and hence $$x^2 = 3\times\text{integer} + 3 + 1 = 3\times(\text{integer} + 1) + 1.$$ We are done.

Let $x = 3k+r, r = 0, 1, 2$ by the division algorithm. Squaring $x$, we find $x^2 = 9k^2+6kr+r^2$, or $x^2 = (9k+6r)k+r^2$.

Since $9k+6r$ is divisible by 3 for all integers $k, r$, then we may re-write this as $x^2 = 3k_1 + r^2$.

Using the division algorithm again, we see that $x^2 = 3k_1+r_1, r_1 = 0, 1, 2$. If $r_1 = 2$, then $r = \pm \sqrt{2}$, which is not an integer. Therefore, only $r=0$ and $r=1$ are acceptable.