Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$ 
Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$. 

I know I have to use Fermat's Little Theorem for this but I am unsure how to do this problem.
 A: As is mentioned in answers above, $gcd(n,6)=1$ clearly implies that $n$ is odd.  But then each of $n+1$ and $n-1$ are even, so $4$ divides $(n+1)(n-1)=n^2-1$.  Thus it is only left to show that $3$ also divides $n^2-1$.  But given any three consecutive integers, we know that $3$ must divide exactly one of them.  Applying this to $n-1,n,n+1$, and using the fact that $3$ cannot divide $n$ (since $gcd(n,6)=1$), we get the desired result. 
A: Can you conclude that $\gcd(n,2)=1$ and $\gcd(n,3)=1$? What about $\gcd(n,4)=1$?
Can you show that $3 \mid n^2-1$ and $4 \mid n^2-1$?   Because if yes, then you're done. Do you know why?
I leave the part $3 \mid n^2-1$ to you, because it's clear I think. Notice that if $\gcd(n,2)=1$ then $n$ must be an odd number. You can write $n^2-1=(n+1)(n-1)$ If $n$ is odd, and it must be if $\gcd(n,2)=1$ then $(n+1)$ and $(n-1)$ will both be even. so $n^2-1$ is divisible by $4$ and $4 \mid n^2-1$.
A: If $\gcd(n,6) = 1$, then $n$ is odd. Hence, $n^2 \equiv 1 \pmod8$. Further, $\gcd(n,3) = 1$ and hence $n^2 \equiv 1 \pmod3$. Now conclude that $n^2 \equiv1 \pmod{24}$.
A: If $\gcd(6,n)=1$ then $n=6k\pm 1$. This yields $$n^2-1=36k^2\pm 12k+1-1=12k(3k\pm 1)$$ So $12\mid n^2-1$.
