Prove that $n^2 \equiv 1 \ (\mathrm{mod}\ 24)$

Question

Let $n$ be an odd integer not divisible by $3$. Prove that $n^2 \equiv 1 \ (\mathrm{mod}\ 24)$. We just started congruences in class so I'm a little stuck as to how to solve this.

So far, I've done: $24 \mid n^2 - 1$ and since $n$ is odd, I defined $n = 2m + 1$ for some integer $m$. Plugging that in gives me $24 \mid 4m(m+1)$, and now I'm not sure what to do with this. Where did I go wrong/any tips on how to solve this?

Answer 1

I'd like to suggest an even better approach: Note that $n^2-1=(n-1)(n+1)$. Since $n$ is odd, $n-1$ and $n+1$ are even and in specific one of these is divisible by $4$. Also, one of $n-1,n,n+1$ is divisible by $3$. By assumption, $n$ is not divisible by $3$, so one of the others must be. Combining all of these gives us the divisibility by $24$.

Answer 2

You're almost done! Note that either $m$ or $m+1$ is even. And either $m$ or $m+1$ is divisible by $3$. (Why? Try modulo $3$.)

Answer 3

$n=6m\pm 1$ so $n^2 =36m^2\pm 12m+1 =12m(3m\pm 1)+1 $ and $m(3m\pm 1)$ is even since if $m$ is odd then $3m\pm 1$ is even.