# Thread: Help I'm stuck with this question:

1. ## Help I'm stuck with this question:

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

2. ## Re: Help I'm stuck with this question:

If $n\not| 2$ or $n\not| 3$, then $n^2(\text{mod} 12) \equiv 1$

Is this what you mean?

3. ## Re: Help I'm stuck with this question:

Originally Posted by mendax05
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

4. ## Re: Help I'm stuck with this question:

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

5. ## Re: Help I'm stuck with this question:

please don't post multiple copies of the same question. I answered this question here as well.