Prove or disprove: if $3\nmid n$ then $3\mid n^2+2$ where $n\in\Bbb N$ I'm new to proofs but I was thinking of doing this proof by contradiction where if $n$ isn't divisible by $3$ then $n^2+2$ also isn't divisible by $3$. But I didn't get very far into that proof. 
 A: Every integer can be written in the form $3k,3k+1$ or $3k+2$.We,don't take $n=3k$ case as it is divisible by $3$.
For $n=3k+1$
$$n^2+2=(3k+1)^2+2=9k^2+6k+3=3(3k^2+2k+1).$$
So,it is divisible by $3$.
For $n=3k+2$,
$$n^2+2=(3k+2)^2+2=9k^2+12k+6=3(3k^2+4k+2)$$.So,it is divisible by $3$.
A: We are to prove that

if $3\nmid n$ then $3\mid n^2+2$.

Any number not divisible by 3 can be written as either $3k+1$ or $3k-1$, where $k$ is an integer. If $n=3k+1$:
$$n^2+2=9k^2+6k+3=3(3k^2+2k+1)$$
If $n=3k-1$:
$$n^2+2=9k^2-6k+3=3(3k^2-2k+1)$$
In both cases, $n^2+2$ can be written as $3m$ where $m$ is an integer. By definition, then, $3$ divides $n^2+2$ and the statement is proved.
A: 2 added to square of remainders of 3 (other than zero), is divisible by 3.
A: We want to proof: if $3\nmid n$ then $3|n^2+2$.
By Fermat's Little Theorem we have:
If $p\nmid n$ then $n^{p-1}\equiv 1\pmod{p}$.
Our problem is when $p=3$,
$$n^2\equiv 1 \pmod{3} \to n^2+2\equiv 1+2\equiv 0 \pmod{3}.$$
We are done!
A: If $3\nmid n \implies n \equiv 1 $ or $n \equiv 2 \space \text{(mod 3)}$. So you have that $$1^{2} + 2 \equiv 3 \equiv 0 \space \text{(mod 3)} $$ $$2^{2} + 2 \equiv 6 \equiv 0 \space \text{(mod 3)}$$
