5
$\begingroup$

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.

$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – user66733
    Sep 23, 2013 at 1:28
  • $\begingroup$ Thanks! I guess it's the result of my not being a number theorist :-) $\endgroup$
    – Doc
    Sep 23, 2013 at 1:35
4
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ how do you know that $n^2$ -1 is divisible by 4 if ($n$ + 1) and ($n$ - 1 are both even? $\endgroup$
    – user72195
    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$
    – user66733
    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$
    – user72195
    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$
    – user66733
    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$
    – user72195
    Sep 23, 2013 at 1:23
4
$\begingroup$

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}$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.