Prove: $3 \nmid n \Leftrightarrow 3 \mid (n^2 -1)$ Been learning how to work with divisibility proofs, and I really need some help understanding this proof. I want to show that $3 \nmid n$ $\Leftrightarrow $ $3 \mid (n^2 -1)$. So, I want to go from say $3 \mid (n^2 -1)$ to $3 \nmid n$ and $3 \nmid n$ to $3 \mid (n^2 -1)$ by proof.
I wanted to start off with $3 \mid (n^2 -1)$ $\implies$ $3 \nmid n$, so I did the following:
If we are given $3 \mid (n^2 -1)$, then $n^2-1=3\cdot a$ for some $a\in \mathbb{Z}$.
This is equivalent to saying $(n-1)(n+1)=3\cdot a$.
So either $(n-1)$ or $(n+1)$  is a multiple of $3$.
Here is where I got a bit stuck, I'm not sure exactly what to do, perhaps considering whether $n$ is odd or even and proceeding from there? I'm even more unsure about the other direction, namely $3 \nmid n$ to $3 \mid (n^2 -1)$. Please help a novice out.
 A: First implication: Write $n=3k+1$, then $(n^2-1)=9k^2+6k$ which can be divided by three.
Otherwise $n$ can be written as $3k+2$ and $(n^2-1)=9k^2+12k+3$.
Reverse direction by contraposition: If $n$ can be written as $3k$, also $n^2$ can be divided by $3$ so $n^2-1$ isn't dividable by $3$. This shows equivalence.
A: You are almost done with your first direction.
When either $(n-1)$ or $(n+1)$ is a multiple of 3 then $n$ cannot be a multiple of 3.
The other direction works analogously. If $n$ is a multiple of 3, then $(n-1)$ and $(n+1)$ cannot be multiples of three and therefore $n^2 -1$ is neither a mulitple of 3.
A: I think its best to approach these problems using modular arithmetic. Denote $a\equiv b \pmod{c}$ as $a=qc+b$ where $q$ is the quotient obtained by dividing $a$ by $c$ and $b$ is the remainder.
Now $3|(n^2-1)$ is the same as saying $n^2-1\equiv 0\pmod{3}$ or $n^2\equiv 1 \pmod{3}.$ Then in general $n\equiv 0\pmod{3}$, $n\equiv 1\pmod{3}$ and $n\equiv 2\pmod{3}$ since these are the only possible remainders that can be obtained by dividing any number by $3.$ On squaring both sides we see that either $n^2 \equiv 0 \pmod{3}$ or $n^2\equiv 1 (\text{or }4) \equiv 1 \pmod{3}$ The first case can only happen if $3|n$ while the second case happens when $n\equiv 1\pmod{3}$ or $n\equiv 2 \pmod{3}$ which is the same as saying that $3$ does not divide $n$.
A: We have three cases $\forall k \in \mathbb Z$

*

*$n=3k \implies 3\mid n \quad \land \quad 3\nmid n^2-1 \:(=9k^2-1)$

*$n=3k+1\implies 3\nmid n \quad \land \quad 3\mid n^2-1\:(=9k^2+6k)$

*$n=3k+2\implies 3\nmid n \quad \land \quad 3\mid n^2-1\:(=9k^2+12k+3)$
which means  $3 \nmid n\iff3 \mid (n^2 -1)$.
