Prove that:
If n is any integer that is not divisible by 2 or 3 then n^2 mod 12 =1?
help i don't know what to do...
$\exists\ p \in \mathbb Z\ such\ that\ n = 3p + k,\ where\ k = 1\ or\ k = 2.$
$CASE\ A:\ k = 1.$
Assume p is odd. Then 3p is odd. So 3p + 1 is even. Thus n is even. But by hypothesis n is not evenly divisible by 2 and so is not even. Contradiction. So p is even.
$\exists\ q \in \mathbb Z\ such\ that\ 2q = p \implies n = 3p + 1 = 6q + 1 \implies$
$n^2 = 36q^2 + 12q + 1 \implies \dfrac{n^2}{12} = \dfrac{36q^2 + 12q + 1}{12} = 3q^2 + q + \dfrac{1}{12}.$ QED
$CASE\ B:\ k = 2.$
Assume p is even. Then 3p is even. So 3p + 2 is even. Thus n is even. But by hypothesis n is not evenly divisible by 2 and so is not even. Contradiction. So p is odd.
$\exists\ q \in \mathbb Z\ such\ that\ 2q + 1 = p \implies n = 3p + 2 = 3(2q + 1) + 2 = 6q + 5 \implies$
$n^2 = 36q^2 + 60q + 25 \implies \dfrac{n^2}{12} = \dfrac{36q^2 + 60q + 25}{12} = 3q^2 + 5q + 2 + \dfrac{1}{12}.$ QED
It finally dawned on me that I made this proof MUCH harder than it needed to be.
What we need is this lemma: for any three successive integers, exactly one is evenly divisible by 3.
$n\ not\ evenly\ divisible\ by\ 2 \implies n + 1\ and\ n - 1\ evenly\ divisible\ by\ 2.$
$n\ not\ evenly\ divisible\ by\ 3 \implies either\ n + 1\ or\ else\ n - 1\ evenly\ divisible\ by\ 3.$
$\therefore n \pm 1\ is\ evenly\ divisible\ by\ 2\ and\ 3 \implies n \pm 1\ is\ evenly\ divisible\ by\ 6 \implies$
$\exists\ p \in \mathbb Z\ such\ that\ 6p = n \pm 1 \implies n = 6p \pm 1 \implies n^2 = 36p^2 \pm 12p + 1 \implies$
$\dfrac{n^2}{12} = \dfrac{36p^2 \pm 12p + 1}{12} = 3p^2 \pm p + \dfrac{1}{12} = an\ integer + \dfrac{1}{12}. QED.$