# What's the explanation for why n^2+1 is never divisible by 3?

What's the explanation for why $n^2+1$ is never divisible by $3$?

There are proofs on this site, but they are either wrong or overcomplicated.

It can be proved very easily by imagining 3 consecutive numbers, $n-1$, $n$, and $n+1$. We know that exactly one of these numbers must be divisible by 3. $$(n-1)(n)(n+1)=(n)(n-1)(n+1)=(n)(n^2-1)$$

Since one of those first numbers had to have been divisible by $3$, this new product $(n)(n^2-1)$ must also be divisible by $3$. That means that either $n$ (and by extension $n^2$) or $n^2-1$ is divisible by $3$. If one of those has to be divisible by $3$, then $n^2+1$ cannot be.

So it is definitely true. My question is why is this true, what is inherent about $1$ more than a square number that makes it not divisible by $3$? Another way of saying this might be to explain it to me as if I don't know algebra.

-
There is nothing complicated about the proof you have shown. What part of the proof bothers you? –  NasuSama Jan 7 at 22:25
I don't understand...you've asked for an explanation for something, then proved it, insist you are correct and finally have ignored that and are asking again why it is true... –  fretty Jan 7 at 22:35
@fretty: calm your temper. There are many ways to prove a theorem and not all proofs are equally good. Some are easy to explain, some are short, some are clever, some are easy to generalize in different directions. Asking for a different proof actually shows a potential in OP. I know great many a student that are satisfied with reading one proof, thinking they know everything there is to know. –  Marek Jan 7 at 22:45
@fretty: it seems to me OP understands the proof perfectly. But knowledge of a topic doesn't come from perfect understanding of one proof but from knowing multiple proofs and how the topic connects with rest of mathematics. As the many answers show, there is much more going on here than meets the eye. Kudos to OP for asking this question. –  Marek Jan 7 at 23:05
But if the OP understands the proof then why say "So it is definitely true. My question is why is this true...". Surely the simplest answer is "because you just proved it". –  fretty Jan 7 at 23:12

Another approach is to write $n=3k+r$, with $r=0$, or $r=1$, or $r=2$, which is always possible: it's a simple division with the remainder. Now, the case $r=0$ is easily settled: $$n^2+1=9k^2+1$$ which can't be divisible by $3$.

If $r=1$, then $$n^2+1=(3k+1)^2+1=9k^2+6k+1+1=3(3k^2+2k)+2$$ which is not divisible by $3$.

If $r=2$, then $$n^2+1=(3k+2)^2+1=9k^2+12k+4+1=3(3k^2+4k)+3+2=3(3k^2+4k+1)+2$$ and again this is not divisible by $3$.

-
Beaten to the same answer. Good for you, +1 :) –  Marek Jan 7 at 22:28
Thought the same thing too, though there are other approaches to show this holds. –  NasuSama Jan 7 at 22:29
I'll just add that the simplest way to see this is of course by using modular arithmetic, since $2^2 \equiv 1^2 \equiv 1 \pmod{3}$. But I guess that doesn't satisfy the requirement of assuming OP doesn't know algebra. –  Marek Jan 7 at 22:31
@Marek Of course this is nothing else than using arithmetic modulo $3$ without telling it. –  egreg Jan 7 at 22:33
Yeah, but the cost of not using that language is that the proof is not a one-liner anymore. Sometimes a little different packaging makes for a very different product :) –  Marek Jan 7 at 22:35

Imagine a big square of dots. It has rows and columns. There is the same number of rows as columns. Plus there's one more dot.

Take three of the rows, and remove them. You have just removed a multiple of three dots - three from each column. Now do the same thing for the rows. Now remove three columns. Again, you've removed a multiple of three. The number of rows and columns is the same again. There's still one more dot.

Keep doing this until there are just $0$,$1$, or $2$ rows and the same number of columns. All the dots you've removed so far can be grouped into a bunch of groups of three. So the square is either $0 \times 0$, $1\times 1$, or $2 \times 2$. So there are either $0+1= 1$, $1+1=2$, or $1+4=5$ dots left. None of these is a multiple of three.

So the whole set of dots consists of a bunch of groups of three, and one group that's not a multiple of three. Clearly, it cannot be a multiple of three.

-
This seems to me to be the most intuitive explanation, but I am a visual person. Still, nice answer; I am surprised it is not voted higher. –  N. Owad Jan 8 at 17:50

one of $n-1,n$ or $n+1$ is divisible by $3$.

If it is $n$ then so is $n^2$.

If it is not $n$, then one of $n-1$ or $n+1$ is divisible by $3$, and hence so is their product $n^2-1$.

Thus, either $n^2$ or $n^2-1$ is a multiple of $3$. If$n^2+1$ would be a multiple of three, then one of $2=(n^2+1)-(n^2-1)$ or $1=(n^2+1)-n^2$ would be a multiple of three.

-
I like the first three paragraphs, although I'd start the first with "For any integer $n$,". Why not conclude with "Thus, for any value of $n$, either $n^2$ or $n^2 - 1$ is a multiple of three, so the next multiple of three above $n^2$ is either $n^2+2$ or $n^2+3$."? –  bryn Jan 8 at 2:27

The key is that taking remainder modulo any fix number (now $3$) doesn't affect the operations $+,-,\cdot$, in that, for instance, if $a$ and $b$ gives the same remainder modulo $m$ (that is, $m$ divides $b-a$), then $a+c$ and $b+c$, or, $ac$ and $bc$ will also give the same remainder modulo $m$. The latter would also imply that $a^2$ gives the same remainder as $b^2$.

So, modulo $3$ now, as the remainders can only be $0,1,2$, if $x$ gives remainder $1$, then so does $x^2$. All we have to compute is $2^2=4$ gives again $1$ remainder. And of course, $0$ gives $0$. So, $2$ is not in the range of squaring modulo $3$.

The relation to give the same remainder modulo $m$ (that is, $m\,|\,b-a$) is called congruence and is denoted by $$a\equiv b\pmod m$$ and also makes sense for negative numbers. For example, $-1\equiv 2\pmod{3}$, and that makes computation even easier: $(-1)^2=1$ (which confirms $-1\equiv 2\ \implies\ (-1)^2\equiv 2^2 \pmod3$ and that no $n^2$ is congruent to $-1$).

-

Let $p$ be an odd prime. Then, if there exists an integer $n$ such that $n^2+1$ is divisible by $p$, it must be that $p-1$ is divisible by $4$.

This requires using Fermat's Little Theorem, which says that $n^p-n$ is always divisible by $p$ (this can be shown using induction and divisibility arguments on binomial coefficients). So, since $n$ cannot be divisible by $p$, $n^{p-1}-1$ is divisible by $p$.

We also need the fact that the set $S=\{k\in\mathbb{N} \mid n^k-1\text{ is divisible by$p$}\}$ must consist of multiples of a single number. You can approach this using group theory, or prove that $\operatorname{gcd}(n^a-1,n^b-1)=n^{\operatorname{gcd}(a,b)}-1$ using the identity $(n^a-1)-(n^b-1)=n^b(n^{a-b}-1)$ for $a>b$.

But we also know that $n^4-1=(n^2+1)(n^2-1)$ is divisible by $p$, and $n^2-1$ is not divisible by $p$ (here is where we use that $p$ is odd). So $S$ consists of exactly the multiples of $4$. Since $p-1\in S$, $p-1$ is a multiple of $4$.

It turns out that the converse is also true: if $p-1$ is divisible by $4$, then there exists an integer $n$ such that $n^2+1$ is divisible by $p$. This is a slightly more advanced fact, but it follows from the existence of primitive roots modulo a prime. If $\zeta$ is a primitive root, then $n=\zeta^{\frac{p-1}{4}}$ is a solution.

Of course, I am assuming that you know some algebra... but this is what is "inherent" about the congruence $n^2\equiv -1$. In the theory of groups, the above proof becomes a single line: "A cyclic group of order $p-1$ has an element of order $4$ if and only if $4$ divides $p-1$."

-
This is the best answer given yet in my opinion. Not necessarily for the OP, but certainly for me because it strikes right at the heart of the problem. –  Marek Jan 7 at 23:07

The simplest explanation follows from Modular Arithmetic.

Any integer must be either $0$, $1$, or $2$ $\pmod{3}$. $n^2+1$ sends these to $1$, $2$, and $2$ $\pmod{3}$. Since none are $0\pmod{3}$, none are divisible by $3$.

-

What is inherent about $1$ more than a square number that makes it not divisible by $3$ ?

About the same that's “inherent” about being $2$ (or $3$) more (or less) than a square number that makes it not divisible by $5$. :-) — And the list could go on, and on, and on, with countless other examples of this sort, all variations on the same theme...

-

If $n=0 \mod 3$ then $n^2+1=1 \mod 3$ so $n^2+1$ is not divisible by $3.$ If $n \neq 0 \mod 3$ then $(n,3)=1$ and we can use the little Fermat theorem. It implies that $n^2=1 \mod 3.$ Thus in this case $n^2+1=2 \mod 3$ and $n^2+1$ also is not divisible by $3$.

-