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

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.

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

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

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

Hint:

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

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

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