$3$ never divides $n^2+1$ Problem: Is it true that $3$ never divides $n^2+1$ for every positive integer $n$? Explain.
Explanation: If $n$ is odd, then $n^2+1$ is even. Hence $3$ never divides $n^2+1$, when $n$ is odd.
If $n$ is even, then $n^2+1$ is odd. So $3$ could divide $n^2+1$.
And that is where I am stuck. I try to plug in numbers for $n$ but I want a more general form of showing that $3$ can't divide $n^2+1$ when $n$ is even.

$n= 0 \pmod3  \implies n^2 + 1 = 1\pmod3$, 
$n = 1\pmod3 \implies n^2 + 1 = 2\pmod3$, 
$n = 2\pmod3 \implies n^2 + 1 = 2\pmod3$. 
So $n^2 + 1$ is not a multiple of $3$ for any $n$.
