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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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