For any integer $a$, there is an integer $k$ such that $a^2=3k$ or $a^2=3k+1$ 
Let $a$ be an integer. Prove that there exists an integer $k$ such that $a^2=3k$ or $a^2=3k+1$.

Here is what I did:
I said: $a\in\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$. When I put 2 into $a^2$, I get $4$ but when I put $2=k$, $3k$, I get the number $4$ on the LHS and the number $6$ on the RHS. But $4$ is not equal to $6$. So how can I prove that $a^2=3k$ equivalent?
I've learned what the division algorithm is. However, when I tried to solve this problem, I got confused.
 A: Hint: The division algorithm tells you that, for any given integer $a$, there exist unique integers $q$ and $r$ such that $$a=3q+r\quad\text{and}\quad 0\leq r<3.$$ Note that the only integers greater than or equal to $0$ and less than $3$ are $0$, $1$, and $2$.  Thus, you know that for any given integer $a$, exactly one of three things is true:


*

*$a=3q+0$ for some integer $q$.

*$a=3q+1$ for some integer $q$.

*$a=3q+2$ for some integer $q$.


In each case, expand $a^2$ and observe which case $a^2$ ends up in. You will see that the last case is impossible. Thus, for any given integer $a$, either


*

*$a^2=3k+0$ for some integer $k$.

*$a^2=3k+1$ for some integer $k$.

A: By division, $\ a = 3j\!+\!r,\ r\in \{0,\color{#c00}{\pm1}\},\,$ so $\,(3j\!+\!r)^2 = 3(3j^2\!+\!2jr)\!+\!r^2,\ r^2\in\{0,\pm1\}^2\! = \{0,1\}$
Note: we used $\ 3j\!+\!2 = 3(j\!+\!1)\!\color{#c00}{-1}$.
A: So, if you divide $a$ by 3, there are only three possible remainders: 0, 1, or 2. So $a$ can be expressed in one of the forms:


*

*$a = 3m + 0$,

*$a = 3m + 1$, or

*$a = 3m + 2$,


where $m$ is some integer that can be found using the Euclidean Algorithm.
If we just accept for the moment that we know $m$, we can try to see the form of $a^2$ for each of these cases:


*

*$a^2 = (3m)^2 = 9m^2$, which if we consider your two cases, this falls under $a^2 = 3k$ if we set $k = 3m^2$. 

*$a^2 = (3m+1)^2 = 9m^2 + 6m + 1$, which can be expanded as $3(3m^2 + 2m) + 1$, and if we set $k = 3m^2 + 2m$, this falls under the $a^2 = 3k + 1$ case.

*$a^2 = (3m+2)^2 = 9m^2 + 12m + 4$, which can be expanded as $3(3m^2 + 6m + 1) + 1$, and if we set $k = (3m^2 + 6m + 1)$, this falls under the $a^2 = 3k + 1$ case.


So you can see that your two cases cover ALL the possible forms of $a^2$, and we're done.
A: I'll try stripping down some of the terminology and keep it as simple as possible. Any integer can be written in the form of $3l$, $3l+1$ or $3l+2$ for some $k\in\mathbb{Z}$. (This follows from the division algorithm.) We don't know which of the three our $a$ happens to be so we need to check what happens when we square it for each case.
Case 1: $a = 3l$.
$a^2 = 9l^2 = 3(3l^2)$. By setting $k = 3l^2$, we have $a^2 = 3k$. This is one of the two possibilities given to us in the problem.
Case 2: $a = 3l+1$.
$a^2 = (3l+1)^2 = 9l^2+6l+1 = 3(3l^2+2l)+1$. By choosing $k=3l^2+2l$, we have $a^2 = 3k+1$, again this is one of the two possibilities given to us in the problem.
Can you see how to do the third one? Do you see how this solves the problem at hand?
A: Note that any integer can be written as one of $3j+0$, $3j+1$, or $3j+2$
$$
\begin{align}
(3j+0)^2&=9j^2&=3k+0&\text{for }k=3j^2\\
(3j+1)^2&=9j^2+6j+1&=3k+1&\text{for }k=3j^2+2j\\
(3j+2)^2&=9j^2+12j+4&=3k+1&\text{for }k=3j^2+4j+1\\
\end{align}
$$
Therefore, the square of any integer can be written as $3k$ or $3k+1$.
Since the tag modular-arithmetic appears in the question, it should be said that the preceding can be written as
$$
\begin{align}
0^2\equiv0\pmod{3}\\
1^2\equiv1\pmod{3}\\
2^2\equiv1\pmod{3}
\end{align}
$$
