Proving for every odd number $x$, $x^2$ is always congruent to $1$ or $9$ modulo $24$ A problem I have been presented with asks the following:
Prove for every odd number $x$, $ x^2$ is always congruent to $1$ or $9$ modulo $24$.
This seems odd and non-intuitive to me. Of course, it must be true other wise they wouldn't be asking for me to prove it.
I know that:
$9$ modulo $24$ $=$ $9$
$1 = 1$
How could every odd number in existence squared be equal to either 1 or 9?

Every number is equivalent mod 24 to one of 0, 1, 2, 3 ,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, or 23.
But our number $n$ is odd, so it is equivalent mod 24 to one of 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23.
Then:
$$\begin{array}{r|r|l}
n & n^2 & n^2\pmod{24}  \\\hline
1 & 1   & 1 \\
3 & 9   & 9 \\
5 & 25 & 1 \\
7 & 49 & 1 \\\hline
9 & 81 & 9 \\
11 & 121 & 1\\
13 & 169 & 1 \\
15 & 225 & 9 \\\hline
17 & 289 & 1 \\
19 & 361 & 1 \\
21 & 441 & 9 \\
23 & 529 & 1
\end{array}
$$
So there you go.
