How to prove if $3\nmid n$, then $n^2$ has a remainder $1$ when divided by $3$? Lets say: 
$n^2=3k+1$ ; $n\neq3$.
I'm trying to prove this by induction, therefore:
$(n+1)^2=n^2+2n+1=3k+2n+2$ 
Any suggestion on how to move foward? 
 A: You don't need induction for this. 
Between 3 consecutive numbers $n-1$, $n$ and $n+1$ there is exactly on divisible by 3. In your case that is $n-1$ or $n+1$ so their product $(n-1)(n+1)=n^2-1$ is divisible by 3. So the remainder when $n^2$ is divided by 3 is 1.
A: You are close here and you need no direct induction: write $\;n=3k+a\;$ , with $\;a\in\{1,2\}\;$ , then
$$n^2=(3k+a)^2=9k^2+6ka+a^2=a^2\pmod 3$$
Now just check that both $\;1^2=2^2=1\pmod 3\;$ and we're done.
A: If 3 does not divide $n$, that means that $n$ has remainder 1 or 2 by division with 3.
So either $n=3k+1$ or $n=3k+2$.
In both cases we have $n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\equiv 1\mod 3$
or $n^2=(3k+2)^2=3(3k^2+4k)+4=3(3k^2+4k)+3\cdot 1+1\equiv 1\mod 3$
A: We can see that $1^2\equiv 1\mod 3$ and $2^2\equiv 1\mod 3$. Now prove that $(a+3)^2\equiv a^2\mod 3$. Now by induction can you see that we have our result? 
A: It's very simple using congruences modulo $3$:  if $n\not\equiv 0\bmod 3$, then $n\equiv 1\;\text{ or }\;2\bmod 3$, so
$$n^2\equiv 1^2=1\;\text{ or }\;2^2=4\equiv 1 \text{ again, }\bmod 3$$
