Prove that for all positive integers $x, \ x$ is not divisible by $3 \iff {x^2 - 1} $ is divisible by $3$.

Question

I am trying to self-study mathematics and I got stuck in this question. I did not find similar questions to this elsewhere so I am asking this one.

Also if you may please answer this follow up question:

Prove using mathematical induction that $x^2 - 1$ is divisible by $3$ for all positive integers $x$ that are not divisible by $3$.

Prove that for all positive integers $x, \ x$ is not divisible by $3 \iff {x^2 - 1} $ is divisible by $3$.

Answer 1

Hint : One of the numbers $x-1,x,x+1$ must be divisible by $3$

Answer 2

Try re-writing $ x^2-1 $ using the difference of two squares: $$ x^2 - 1 = (x+1)(x-1)$$ If we know that this is a multiple of 3, then what can you say about $x+1$ and $x-1$?

Answer 3

Hint:

The sequence of $(n^2-1)\bmod 3$ is $2,0,0,2,0,0,2,0,0,\cdots$

Answer 4

$\Leftarrow:$

Assume $3|(x^2-1)$;

Then $3|(x-1)(x+1)$;

Euclid's lemma:

$3|(x-1)$ or $3|(x+1)$, hence $3 \not | x$;

$\Rightarrow:$

Assume $3\not | x$;

We have $3| (x-1)(x)(x+1)$, three consecutive integers.

Euclid's lemma:

$3|(x-1)$ or $3|(x+1)$, hence

$3|(x-1)(x+1)$, and we are done.

Answer 5

Use congruences:

A number $x$ is divisible by $3$ iff $x\equiv 0\bmod 3$. A number $x$ is not divisible by $3$ iff $x\equiv 1$ or $-1\bmod 3$, and in this single case, $x^2\equiv 1\bmod 3$.