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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.
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$.