<s>[INST] $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.
 [/INST] Every integer $n$
can be written in the form
$3m+k$,
where $m$ is a non-negative integer
and $k = 0, 1, $ or $2$.
(This is a particular case of
the result that
for any positive integer $j$,
every integer $n$
can be written in the form
$jm+k$, where  $m$ is a non-negative integer
and $k$ is an integer such that
$0 \le k < j$.)
Therefore
$n^2+1
=(3m+k)^2+1
=9m^2+6mk+k^2+1
=3(3m^2+2mk)+k^2+1
$.
If $3 \mid n^2+1$,
then $3 \mid k^2+1$.
But
the possible values of
$k^2+1$ are
$1, 2, $ and $5$
(for $k = 0, 1, 2$, respectively),
and $3$ does not divide any of them.
Therefore $3$ does not divide $n^2+1$.
</s>