prove that $3$ does not divide $n^2+1$

Question

How do I prove that $3$ does not divide $n^2+1$, for all $n\in\mathbb{Z}$, thought of in separate cases, but did not get, induction also was unable to ....

Answer 1

Hint:

The squares of the elements in $\mathbb{Z}/3\mathbb{Z}$ are $\bar{0}^2=\bar{0},\bar{1}^2=\bar{1},\bar{2}^2=\bar{1}$.

Answer 2

I don't know if you know modular arithmetic or not, but write $n = 3k + r$ where $r$ is $0, 1, $ or $2$. Then $n^2 = (3k + r)^2 = 9k^2 + 6kr + r^2 = 3k' + r^2$, where $k'$ is a different number as you see. So $n^2 + 1 = 3k' + r^2 + 1$. What can $r^2$ possibly be? Well, $r$ can be $0, 1,$ or $2$. In which case you have $r^2 + 1 = 1$, $2$ or $5$. In none of these cases do you see that 3 divides $n^2 + 1$. If you know modular arithmetic, see user1337's post.

Answer 3

Hint:

For 3 to divide $n^2 + 1$ then $n^2+1$ must be of the form 3k. Then look at $n^2$ for any integer of the form $2k$ or $2k+1$. $(2k)^2 = 4k^2$ or $2(2k^2)$, even, and $(2k+1)^2 = (2k+1)(2k+1) = 4k^2+4k+1 = 2(2k^2+2k)+1$, odd.

You can then easily see that any integer of the form $n^2+1$ is either of the form $2k+1$ or $2k+2$, and clearly neither are divisible by 3.

Answer 4

Here is a stronger result:

If a prime $3 \pmod 4$ divides the sum of two integer squares, it must also divide each of those squares.

Answer 5

Suppose $\,3\mid \color{#0a0}{n^2+1}.\ $ Note $3$ divides one of $\,n\!-\!1,\ n,\ n\!+\!1.\,$ But $\,3\nmid \color{#c00}n\,$ else $\,3\mid 1 = \color{#0a0}{n^2+1}-\color{#c00}n\cdot n$. Hence $\,3\mid \color{#c0d}{n\!-\!1}\,$ or $\,3\mid \color{#c0d}{n\!+\!1}\,$ so $\,3\mid 2 = \color{#0a0}{n^2+1}-\color{#c0d}{(n\!-\!1)(n\!+\!1)},\,$ contradiction

Said modly, $\ {\rm mod}\ 3\!:\ \color{#c00}{n\equiv 0}\,\Rightarrow\, n^2+1\equiv 1,\ $ and $\, \color{#c0d}{n\equiv \pm1} \,\Rightarrow\, n^2+1\equiv 2$