# Show that if $n$ is odd and isn't divisible by $3$ then $n^2 \equiv 1 (\bmod 24)$ [duplicate]

what I have so far is that:

$n = 3q+r$,

$r≠0$ (otherwise it is divisible by 3)

$r=1$ (when $q$ even)

$r=2$ (when $q$ is odd)

So, $n_1 = 3(2k+1)+2 = 6k+5$

$n_2 = 3(2k)+1 = 6k+1$

$n_1^2 = 36k^2 +60k +25 = 12(3k^2 + 5k + 2) + 1$

$n_2^2 = 36k^2 +12k +1 = 12(3k^2 + k) + 1$

Then I don't know where to go from here as this only shows that they are congruent to 1 mod 12.

• ${\rm mod}\ 2\!:\,\ k^2\equiv k\,$ so $\,3k^2+k\equiv 3k+k\equiv 0\ \$ – Gone Dec 3 '16 at 4:09

$n$ is odd and not divisible by $3 \implies n=6k\pm 1$
$(6k \pm1 )^2 = 36k^2 \pm 12k +1 = 12k(3k\pm 1) +1$
Since one of $k$ and $(3k\pm1)$ must be even, $24 \mid 12k(3k\pm1)$ and thus $n^2 \equiv 1 \bmod 24$