$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.
 A: 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).
A: Hint: What are the only squares modulo $3$? Put another way, look at the expression $n^{2}+1$ modulo $3$. What is true of $n^{2} \pmod 3$ for any $n \in \mathbb{N}$?
A: If $3$ divides $n^2+1$ then it must have solution modulo $3$. But clearly
$0^2+1\equiv 1 \pmod 3$
$1^2+1 \equiv 2 \pmod 3$
$2^2+1 \equiv 5 \equiv 2 \pmod 3$ 
Otherwise put $n=3k,3k+1,3k+2$ and see that $3$ never divides it
A: Instead of considering whether $n$ is even or odd, consider the remainder when $n$ is divided by $3$; as an example, if the remainder is $1$, we have $$n = 3k + 1 \implies n^2 + 1 = 9k^2 + 6k + 2$$
which is not divisible by $3$. There are two more cases.
A: $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$.
A: 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$.
A: Divide $n$ by $3$ and let $Q$ be the quotient and $R$ the remainder. So
$$ n = 3\,Q + R$$
$$n^2+1 = 9\,Q^2 + 6 \, Q\, R + R^2 +1$$
$R$ can only be $0$, or $1$ or $2$. Now argue that in all cases $n^2+1$ is not divisible by $3$.
Not divisibility depends only on $R$ i.e. only on $n \mod 3$. From your question, it looks like you are just starting on number theory. You will soon realize that most problems require you to look only at the remainder.
A: Since $n-1,n,n+1$ are three successive integers so one of them must be divisible by 3 hence there product must be divisible by $3$ i.e. $3|(n-1)n(n+1) \implies 3|n^3-n$ , now 
$3|n^2+1 \implies 3|n(n^2+1) \implies 3|n^3+n \implies 3|n^3+n-(n^3-n) \implies 3|2n$ , since 3 does 
not divide $2$ so $3|n \implies 3|n^2 \implies 3|n^2+1-n^2 \implies 3|1$ , contradiction ! 
A: Note that the statement mathematically means: $$ 3 \mid (n^2 + 1) \implies n^2 + 1 \equiv 0 \pmod 3 \equiv n^2 \equiv -1 \equiv 2 \pmod 3. $$ Is this ever possible? 
A: $\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
For $n = 1$, it's obvious since $3 \not|\ 2$. Let's assume $3 \not|\ n^{2} + 1$. Then, $n^{2} + 1 = 3p + \delta$ for $p, \delta$ integers and $\delta = 1, 2$:
$$
\pars{n + 1}^{2} + 1 = n^{2} + 1 + 2n + 1 = 3p + \delta + 2n + 1
$$ 
If $\delta = 1$, $\delta + 2n + 1 = 2\pars{n + 1}$ which is even. 
If $\delta = 2$, $\delta + 2n + 1 = 2n + 3\quad\imp\pars{n + 1}^{2} + 1 = 3\pars{p + 1} + 2n$: The first term is a multiple of $3$ but the second is even. 
