Prove that:

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

Results 1 to 2 of 2

- Apr 10th 2014, 04:42 PM #1

- Joined
- Apr 2014
- From
- Canada
- Posts
- 4

- Apr 11th 2014, 04:08 AM #2

- Joined
- Nov 2013
- From
- California
- Posts
- 6,318
- Thanks
- 2712

## Re: 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