# Proving that $x^2 + 4$ is not divisible by $3$

I need to show the following:

For any integer $x$, $x^2 + 4$ is not divisible by $3$.

I was trying proof by contraposition, but I do not believe that is the most efficient way to go about this. Can anybody point me in the right direction, please?

• hint: Consider $0^2, 1^2$ and $2^2$ $\mod 3$. – sranthrop Apr 28 '15 at 3:43

Assume that $x^4 +4$ is divisible by $3$. Then $x^2 + 1 = (x^2 +4) -3$ is divisible by $3$.

Now (following https://math.stackexchange.com/a/630761/26188) you have that one of the following is divisible by $3$:

• $x-1$
• $x$
• $x+1$. If $x$ is divisible by $3$, then so is $x^2$ and so $x^2 + 1$ would not be divisible by $3$.

If $x$ is not divisible by $3$, then $x-1$ or $x+1$ would be divisible by $3$. So $(x-1)(x+1) = x^2 -1$ is divisible by $3$. And so then $x^2 + 1 = (x^2 -1) +2$ can't be divisible by $3$.

For any $n \in \mathbb{N}$, we have $n \equiv 0,1,2 \text{ mod } 3$. Hence $n^2 \equiv 0,1 \text{ mod } 3$. Thus $n^2+4 \equiv 1,2 \neq 0 \text{ mod } 3$. So for any integer $n \in \mathbb{N}$ , $n^2+4$ is not divisible by $3$.

If you like, you can do this as an exercise in proof by infinite descent. Suppose there were such an $x$. Since we're squaring it, we can assume $x\ge0$, and it's easy to see that we can assume $x\ge3$ as well, since $4$, $5$, and $8$ are not divisible by $3$. But if $x^2+4=3k$, then

$$(x-3)^2+4=x^2+4-6x+9=3(k+2x+3)$$

which means there is no minimal counterexample, hence no counterexamples at all.

$$x \equiv 0 \equiv 1 \equiv -1 \pmod{3} \space \text{for all cases}$$

Then:

$$x^2 \equiv 0 \equiv 1 \equiv 1 \pmod{3}$$

In any of the cases,

$$4 \equiv 1 \pmod{3}$$

$$x^2 + 4 \equiv 1 \equiv 2 \equiv 2 \pmod{3}$$

ALSO:

$$x^2 + 4 = (x + 2)^2 - 4x$$

Suppose it is divisible by $3$ then,

$$x + 2 \equiv 2\sqrt{x} \pmod{3}$$

But $\sqrt{x}$ isn't necessarily an integer, but a remainder is always an integer.