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.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ +1 for the last part...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. I like how you did it without Fermat's little theorem. $\endgroup$ Sep 23, 2013 at 1:28
-
$\begingroup$ Thanks! I guess it's the result of my not being a number theorist :-) $\endgroup$– DocSep 23, 2013 at 1:35
$\begingroup$
$\endgroup$
6
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$.
-
$\begingroup$ how do you know that $n^2$ -1 is divisible by 4 if ($n$ + 1) and ($n$ - 1 are both even? $\endgroup$ Sep 23, 2013 at 1:05
-
1$\begingroup$ @user72195 because we can write $n+1=2k$ and $n-1=2q$. If you multiply them $n^2-1 = (n+1)(n-1) = 4kq$ which means $n^2-1$ is divisible by 4. You can also say it in essentially the same way with a different appearance that if $a \mid c$ and $b \mid d$ then $ab \mid bc$. So, if $2 \mid n+1$ and $2 \mid n-1$ then $4 \mid n^2-1$. $\endgroup$ Sep 23, 2013 at 1:07
-
$\begingroup$ since we know that 3 and $n$ are relativily prime to each other, is that why 3|$n^2$ - 1? $\endgroup$ Sep 23, 2013 at 1:17
-
$\begingroup$ @user72195 Yes. You need $(3,n)=1$ that you can apply Fermat's little theorem. Once you know that then notice that $3|n^2-1$ is the same as $n^{3-1} \equiv 1 \pmod{3}$ and we know the later one is true because of Fermat's little theorem. $\endgroup$ Sep 23, 2013 at 1:19
-
$\begingroup$ okay. So now I have concluded that 12|($n^2$-1)($n^2$-1) but how does that show 12|($n^2$-1)? $\endgroup$ Sep 23, 2013 at 1:23
$\begingroup$
$\endgroup$
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}$.
$\begingroup$
$\endgroup$
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$.
answered Jul 25, 2018 at 22:06