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?
 A: When in doubt, you can simply square all of the odd numbers 1, 3, 5, up to 23, and verify that each one is congruent to either 1 or 9 modulo 24. What follows is a trick, which will get you the result much more quickly.
Write $(2k+1)^2 = 4k^2 + 4k+1 = 4k(k+1)+1$.
The claim then is that for all $k$, $24$ divides either $(2k+1)^2-1 = [4k(k+1)+1]-1 = 4k(k+1)$ or $(2k+1)^2-9 = [4k(k+1)+1-9] = 4k(k+1)-8 = 4[k(k+1)-2]$. From the fact that either $k$ or $k+1$ is even, notice that $8$ divides both quantities. So it is sufficient to see that $3$ divides one or the other. Now consider cases based on whether $k \equiv 0, 1,$ or $2 \mod 3$.
A: Based on your comments to the first answer, you may need a further review of the modulo concept.  There are many resources so I will leave you to use your favorite or use a search engine.
As stated in other answers, the most straightforward way to verify the claim is to square each number from 1 to 23 (or -11 to 11) and reduce the result modulo 24.  However, I will show you a method that makes problems with much larger numbers manageable.
The key is to realize that conditions modulo different moduli are independent for coprime moduli.  Therefore, you can first show that all odd squares are $1 \mod 8$ by only checking four values.  You can then show that all squares are $0$ or $1\mod 3$ (realizing that you must check all values since you cannot tell which numbers are even mod 3).  You can then combine these conditions as follows: the numbers less than 24 which are 0 or 1 mod 3 are: $$ 0,1,3,4,6,7,9,10,12,13,15,16,18,19,21,22$$ and the numbers which are 1 mod 8 are: $$ 1,9, 17$$ the only numbers which are in both lists are 1 and 9, therefore these are the only numbers which may be squares modulo 24.
A: Since we are told that x is odd, then there are only six cases of congruence: $x\equiv\pm1,\pm3,\pm5,\pm7,$ $\pm9,\pm11\mod 24$. In the first case, $x^2\equiv1^2\equiv1\mod24$. In the second, $x^2\equiv3^2\equiv9\text{ mod } 24$. In the third, $x^2\equiv5^2\equiv25\equiv(24+1)\equiv1\mod24$. In the fourth, $x^2\equiv7^2\equiv49\equiv(2\cdot24+1)$ $\equiv1\mod24$. In the fifth case, $x^2\equiv9^2\equiv81\equiv(3\cdot24+9)\equiv9\mod24$. In the last case, $x^2$ $\equiv11^2\equiv121\equiv(5\cdot24+1)\equiv1\mod24$. QED. Obviously, if the remainder $\mod24$ would be even, then the entire number would also be even. And the square of a negative number is the same as that of its positive counterpart. Hence the reduction in the total number of distinct cases.
A: Hint: write $x = 2k+1$, where $k$ is an integer. Any odd integer can be written this way. Expand $x^2$, consider cases depending on parity of $k$.
A: Since $x$ is of the form $2n+1$ for some $n$, we want to find:
$$4n(n+1)+1 \ (\textrm{mod} 24)$$
If $n$ is divisible by $3$, we know that $4n(n+1)$ is divisible by $4n$ (and therefore by $12$, and also by $n+1$ (and therefore by $2$), so:
$$ 3 | n \longrightarrow 4n(n+1)+1 \ (\textrm{mod} 24) \equiv 0 +1\equiv1$$
A similar analysis can be done for the cases $n\  \textrm{mod} \ 3 \equiv 1,2$.
A: 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.
A: $$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$.
