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

-
An even number may or may not be divisible by $3$. For example, $6$ is even and divisible by $3$. – Michael Albanese Dec 28 '13 at 4:27
In a similar manner, prove that $5$ never divides $n^2+2$ and $n^2+3$. – Lucian Dec 28 '13 at 5:29

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.

-

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}$?

-
But there are three results. that $n^2$ is congruent to 0,1,2 – Username Unknown Dec 28 '13 at 4:29
Can you give me an example of $n$ such that $n^{2} \equiv 2 \pmod 3$? ;) (To prove there is no such $n$, use the fact that congruence classes are multiplicative: for each $n$, $n$ is congruent to $0, 1,$ or $2 \pmod 3$. Then compute $n^{2}$ in each case. $0$ and $1$ are obvious. But $2^{2} = 4 \equiv 1 \pmod 3$) – Alex Wertheim Dec 28 '13 at 4:30

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

-

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

-

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

-

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.

-

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 !

-

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

-

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?

-

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

-

I agree with all your answers above, but I need someone to point out my error in the following construction;
assume $3|n^2+1$, then we can find an integer $m^2$ such that $n^2+1=3m^2$, so that we arrive at the negative Pell's equation; $n^2-3m^2=-1$, for which there exist infinitely many solutions, showing that m and n actually exist.

-
Just because $3\mid x^2+1$ it does not follow that the quotient should be a square. – Old John Dec 28 '13 at 11:15
Also, that negative Pell equation does not have infinitely many solutions, it has none. – Old John Dec 28 '13 at 11:25
I don't want to put you off, but on this site, an answer isn't meant to be a question itself. – barto Dec 28 '13 at 16:27