Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

11 Answers 11

up vote 23 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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 !

share|cite|improve this answer

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

share|cite|improve this answer

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?

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.