If $n$ is odd and $3\not\mid n \Rightarrow \ 3\mid n+1 \text{ or } 3\mid n-1 $ I'm proving that:
If $3\not\mid n$ and $n$ is odd $\Rightarrow 6\mid n^2 - 1$
First, I do this:
$$n^2 - 1 = (n-1)(n+1) $$ If the original proposition is true, then by unique factorization in $\mathbb{Z}$ it must be satisfied that: $$3\mid(n-1) \text{ or } 3\mid(n+1)$$
But I can't prove this fact. Can anyone help me? Thanks.
 A: $3\not\mid n$ and $n$ is odd $\iff$ $n$ is of the form $6k\pm1$.
In this case, $n^2-1 = 36k^2+12k$ is a multiple of $6$ (it is even a multiple of $24$).
A: that $3|n-1$ or $3|n+1$ follows from the division alg.  as $n$ is of the form $3q+r$, $r\in\{{1,2}\}.$  that $2$ divides $(n-1)(n+1)$ follows from this being even as $n$ is odd.  
A: For sake of contradiction, presume $!(3|n-1$ or $3|n+1)$.
By DeMorgan's Law, $!(3|n-1$ or $3|n+1) \leftrightarrow !(3|n-1)$ and $!(3|n+1)$.
n is odd $\rightarrow$ n is an integer $\rightarrow$ $n (mod3) \in  \{0, 1, 2\}$
This gives 3 cases:
Case 1:
$n(mod3) = 0 \rightarrow 3|n$ which contradicts $!(3|n)$
Case 2:
$n(mod3) = 1 \rightarrow n-1(mod3) = 1-1\rightarrow n-1(mod3) = 0 \rightarrow 3|n-1 $ which contradicts $!(3|n-1)$.
Case 3:
$n(mod3) = 2 \rightarrow n+1(mod3) = 2+1 \rightarrow n+1(mod3) = 3 \rightarrow n+1(mod3) = 0 \rightarrow 3|n+1$ which contradicts $!(3|n+1)$.
Since all cases lead to a contradiction, 
$(3|n-1$ or $3|n+1)$.
A: Can you just look at $\mathbb{Z}$ modulo 3 and 2?
You know that $n^2 \equiv 1( mod \ 3)$ and that $n\equiv 1 (mod \ 2)$.
That's all the knowledge you need.
A: Any positive integer is of the form 3m,3m+ 1, or 3m+ 2.  But 2= 3- 1 so this can also be written 3m+ 3- 1= 3(m+ 1)- 1.  So any positive integer can be written 3m, 3m+ 1, or 3m- 1.  If 3 does not divide n, n is of the form 3m+ 1 or 3m- 1.  Further, if n is odd, then n- 1= 3m+ 1- 1= 3m or 3m-1- 1= 3m- 2, n+ 1= 3m+ 1+ 1= 3m+ 2 or 3m-1+ 1= 3m must be even. That means that m itself must be even so m= 2k and n= 3m+1= 6k+ 1 or n= 3m- 1= 6k- 1.  
In the case n= 6k+ 1, n^2- 1= 36k^2+ 12k+ 1- 1= 36k^2+ 12k= 6(6k^2+ 2k).
In the case n= 6k- 1, n^2- 1= 36k^2- 12k+ 1- 1= 36k^2- 12k= 6(6k^2- 2k).
In fact, it looks like you can say more- if n is an odd number, not divisible by 3, then n^2- 1 is divisible by 12.
