0
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.