Prove that for every $n\in\mathbb{N}$, $n^2$ is divisible by 3 or has a form $3k+1$? I tried to do this by induction, but it doesn't make any sense:  $n^2=3k$ or $n^2=3k+1$ 


*

*option: $(n+1)^2= 3k+2n+1$ 

*option: $(n+1)^2= 3k+2n+2$
Is there any other way on proving this problem?
 A: For some integer $m$, one of the following must be true:


*

*$n = 3m$

*$n = 3m + 1$

*$n = 3m + 2$
In case $1$), it should be clear that $n^2$ is divisible by $3$.
In case $2$), we have $n^2 = (3m + 1)^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1$, so with $k = 3m^2 + 2m$, we have $n^2 = 3k + 1$.
Can you complete case $3$?
A: For all $n$ natural number, $n = 3k$ or $n=3k+1$ or $n=3k+2$
When $n=3k$, $n^2=9k^2=3(3k^2)$, thus is divisible by 3
When $n=3k+1$, $n^2=9k^2+6k+1=3(3k^2+2k)+1$, thus is in the form of $3n+1$
When $n=3k+2$, $n^2=9k^2+12k+4=3(3k^2+4k+1)+1$, thus is in the form of $3n+1$
Thus, covering all the cases and finishing the proof
A: $2=-1$ is not  perfect square modulo $3$ because $3$ is not congruent to $1$ modulo $4$. This is a consequence of the quadratic reciprocity law. This leaves you with the two possibilities: $n^2 = 0$ (mod 3) or $n^2 = 1$ (mod 3).
A: Every $n \in \mathbb{N}$ must be of one of the following forms:
$3k$ or $3k+1$ or $3k+2$
Can you see the following:
If $n$ is of the form $3k$, then $n^2$ is also of the form $3k$
If $n$ is of the form $3k + 1$, then $n^2$ is also of the form $3k + 1$
If $n$ is of the form $3k + 2$, then $n^2$ is also of the form $3k + 1$
That completes the proof!
A: Because you wanted to proceed by induction ...
Base case: $0^3 = 0$ is divisible by 3
For any $n$, we have 2 cases.
First take $(n + 1)^2 = n^2 + 2n + 1$
Case 1: $n^2$ is divisible by 3
Let $n = 3k$. What can we conclude?
Case 2: $n^2$ is $3k + 1$. 
$$ n^2 + 2n + 1 = n^2 - 1 + 2(n + 1) = (n - 1)(n + 1) + 2(n + 1)$$
We know $n$ is even as $n^2$ is even (fundamental theorem of arithmetic). 
Then if $n + 1$ is divisible by 3, we are done.
If $n + 1$ is not, then because $n$ is even, for odd $m$, $n + 1 = 3m + 2$. 
$$2(n + 1) = 2(3m + 2 + 1) = 2(3m + 3) = 6m + 6$$.
And you can see that it is divisible by 3.
A: In terms of 3 n can only be two things:
$3k, 3k \pm 1$
The remainders of n divided by 3 are either $0$ and $\pm 1$
This is modular arithmetic in it's basic form. Expanding the first leads to a term divisible by $3$, expanding the second has terms divisible by 3 and then the $1^2$. Hence thy conjecture.
