# Why is $x^2+1$ not divisible by 3?

I am unable to answer this question. I have searched online for solutions to this but have unfortunately not found any. Most likely because I had to use the fact that an integer has one of these three forms. $3n$, $3n+1$, and $3n+2$. Could anyone help me solve this problem?

• You can try that x is any of those three forms and see what happens when you simplify the expressions you get. Take them one at a time. – mathreadler Sep 27 '17 at 19:27
• You could evaluate the expression $x^2+1$ for the three forms you gave and see what happen. – Bérénice Sep 27 '17 at 19:27
• The most elegant way is to compute the legendre symbol $(\frac{-1}{3})$, but there are easier ways to see it. – Peter Sep 27 '17 at 19:32
• @Peter : That sounds interesting, do you have a reference to legendre symbols for me? – mathreadler Sep 27 '17 at 19:47
• @mathreadler mathworld.wolfram.com/LegendreSymbol.html – Peter Sep 27 '17 at 19:50

Hint : Take $(3k)^2+1$ , $(3k+1)^2+1$ , $(3k+2)^2+1$ modulo $3$ or just use that $x^2\equiv 0$ or $1\mod 3$

all integers $\mathbb{Z}$ can be classified as members of one of the following classes:
$$C_0=3k$$ $$C_1=3k+1$$ $$C_2=3k+2$$ Such that $\ k\in \mathbb{Z}$.

So all numbers divisible by $3$ can be seen as belonging in $\ C_0$

Yet, squaring each class and adding $1$:

\begin{align}3k &\to (3k)^2 + 1 &&=9k^2+1 &&=3(3k^2)+1 \in C_1\\ 3k+1 &\to(3k+1)^2 + 1 &&=9k^2+6k+2 &&=3(3k^2+2k)+2\in C_2 \\ 3k+2 &\to(3k+2)^2 + 1 &&=9k^2+12k+5 &&=3(3k^2+4k+1)+2\in C_2\end{align}

We find that none of the three possible classes yielded anything belonging in $\ C_0$

$\text{If}\quad n\in \mathbb{N}\rightarrow \exists k\in \mathbb{N}\cup \{ 0\}/\left\{ \begin{array}{lcc} n=3k \\ \\ \vee \\ \\ n=3k+1 \\ \\ \vee \\ \\ n=3k+2 \end{array} \right.\rightarrow \left\{ \begin{array}{lcc} n^{2}+1=9k^{2}+1=3(3k^{2})+1\neq 3 \\ \\ \vee \\ \\ n^{2}+1=(3k+1)^{2}+1=3(3k^{2}+2k)+2\neq 3 \\ \\ \vee \\ \\ n^{2}+1=(3k^{2}+2)^{2}+1=3(3k^{2}+4k+1)+2\neq 3 \end{array} \right.\rightarrow n^{2}+1\neq 3$

an integer has one of these three forms. $3n$, $3n + 1$, and $3n + 2$

Why don't you try squaring those three forms and seeing what happens?

$(3n)^2 = 9n^2$. That's definitely a multiple of $3$. But $9n^2 + 1$ is not.

$(3n + 1)^2 = (3n + 1)(3n + 1) = 9n^2 + 6n + 1$, so $(3n + 1)^2 + 1 = 9n^2 + 6n + 2$, and that's not a multiple of $3$ either.

You should now be able to do $(3n + 2)^2 + 1$ on your own.

Just a little clarification first: $x$ has to be an integer from $\mathbb Z$, right? Because if not, we can do $x = \sqrt 2$, $i$, $\sqrt{-7}$, etc.

With the restriction to integers, $x \in \mathbb Z$, we can focus our attention on 0 and the positive integers, since negative integers square to positive integers anyway.

So here's yet another way to get at the same answer: do the arithmetic in ternary. You know about decimal and binary, right? Ternary is pretty much just like binary, except we can also use the digit 2, and each place corresponds to powers of 3.

So, for example, 7 in ternary is 21. Then $$\begin{equation*}\begin{array}{c} \phantom{\times999}21 \\ \underline{\times\phantom{999}21}\\ \phantom{\times99}21\\ \underline{\phantom\times 112\phantom9}\\ \phantom\times 1211 \end{array}\end{equation*}$$

If I did that correctly, 2211 in ternary should equal 49 decimal. Then 50 is 1212, which is definitely not a multiple of 3.

Okay, how about 8, which is 22, here goes: $$\begin{equation*}\begin{array}{c} \phantom{\times999}22 \\ \underline{\times\phantom{999}22}\\ \phantom{\times99}121\\ \underline{\phantom{\times9} 121\phantom9}\\ \phantom\times 2101 \end{array}\end{equation*}$$

This shows that if $x$ is an integer, then the ternary representation of $x^2 + 1$ ends in 1 or 2, but not 0.

Because, according to Euler's theorem $$x^{\varphi{(3)}} \equiv 1 \pmod{3}$$ when $\gcd(x,3)=1$. This means $3 \mid (x^2-1)$, because $\varphi(3)=2$. If we assume $3 \mid (x^2+1)$, we end with $3 \mid 2$ which is a contradiction.

When $\gcd(x,3)>1$, we have $3 \mid x$, since $3$ is prime. If we assume $3 \mid (x^2+1)$, we end with $3 \mid1$ which is a contradiction as well.

That is because $-1$ is not a square modulo $3$: indeed the squares modulo $3$ are congruent to $$0^2=0,\quad (\pm 1)^2=1.$$

Hint: $$\begin{array}{c|c} n\pmod{3}&n^2+1\pmod{3}\\\hline 0&1\\ 1&2\\ 2&2 \end{array}$$