Prove that:

If n is any integer that is not divisible by 2 or 3 then n^2 mod 12 =1?

Printable View

- Apr 10th 2014, 04:42 PMmendax05help i don't know what to do...
Prove that:

If n is any integer that is not divisible by 2 or 3 then n^2 mod 12 =1? - Apr 11th 2014, 04:08 AMromsekRe: help i don't know what to do...
Consider $p=(n-1)(n+1)$

2 doesn't divide $n$ so it must divide both $(n-1)$ and $(n+1)$. So let $(n-1)=2k$ and $(n+1)=2(k+1)$

3 doesn't divide $n$ so it must divide either $n-1$ or $n+1$ (but not both). Let's suppose for now that $n-1=3m$

$(n-1)(n+1)=(2k)\left(2(k+1)\right)(3m) = 12k(k+1)m= 12\left(k(k+1)m\right)$

$n^2 - 1=12\left(k(k+1)m\right)$

$n^2 = 1 + 12\left(k(k+1)m\right)$

$n^2 = 1 (\bmod~12)$

if it's such that $n+1=3m$ the result is the same