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?

$$x^2-1=(x-1)(x+1)$$
is the product of two consecutive even numbers. Thus, one is multiple of $4$ and the other is even. This shows that $x^2-1$is a multiple of $8$.
Moreover, one of $x-1,x,x+1$ is  a multiple of three. 
Case 1: $x$ is not a multiple of $3$. Then $x^2-1$ must be a multiple of three. Thus
$x^2-1$ is a multiple of $24$.
Case 2: $x$ is a multiple of $3$. Then $x^2$ is a multiple of $9$. In this case we have
$$9|x^2 \, \mbox{and}\, 8 |x^2-1 \,.$$
Then
$$9| x^2-9 \, \mbox{and}\, 8 |x^2-9 \,.$$
thus
$$72|x^2-9 \,.$$
In this case $x^2-1$ is a multiple of $72$ hence of $24$.
