$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.

Another way: $ $ notice that $\,3\,$ divides one of $\ \color{#0a0}{n\!-\!1,\,n,\,n\!+\!1}.\ $ Therefore
$\ \ \ \color{#c00}{3\mid n^2\!+1}\Rightarrow\ 3\mid 2 = (\color{#c00}{n^2\!+1})(2\!-\!n^2)+\color{#0a0}{(n\!-\!1)n^2(n\!+\!1)},\ $ contradiction.
Remark $\ $ The above implies coprime $\,n^2\!+1\,$ and $\,n^3\!-n = (n\!-\!1)n(n\!+\!1),\,$ except when $\,n\,$ is odd, when they have gcd $= 2.\,$ The above linear relation between them is simply the Bezout identity for their gcd, considered as a polynomial over $\Bbb Q$ (which can be computed mechanically using the extended Euclidean algorithm). Though this approach is not as efficient as using modular arithmetic, it highlights an interesting viewpoint that often proves useful: often properties of integers (numbers) are special cases of properties of polynomials (functions).
