CRT Solving $x^2 \equiv 1 $ (mod m) m = 24, 25, 64 
c) Find all solutions to the congruence $x^2 ≡ 1$ (mod m) for
(i) m = 24;
(ii) m = 25;
(iii) m = 64.

For (i), I split $24 = 3*8$. and brute-force calculated all $x^2 \equiv 1$ (mod 8) as $x \in \{1,3,-1,-3\}$ and all $x^2 \equiv 1$ (mod 3) are $x \in \{1, -1\}$.
Since $1 = 3.3 -8 $ the solutions are $\{\pm 3.3 \pm 8, \pm 3.3 \pm 3.8\} = \{\pm 1, \pm 11, \pm 17, \pm 19 \}$
For (ii) I can solve $x^2 \equiv 1$ (mod 5) for $ x = \pm 1$ (mod 5) and then if $(5k \pm 1)^2 \equiv 1 $ (mod 25) then $10k \equiv 0$ (mod 25) so $k \in \{0,5,..\} $ and $x = \pm 1$ (mod 25)
Now (iii) can be solved like (ii). $(8k \pm 1)^2 \equiv 1$ (mod 64) $\Rightarrow$ $16k \equiv 0$ (mod 64) so $ k \in \{0,4,..\}$, and $(8k \pm 3)^2 \equiv 1$ (mod 64) $\Rightarrow$ $ \pm 2.3.8k + 8 \equiv 0$ (mod 64), so $8(6k + 1) \equiv 0$ (mod 64) (no solutions)
This all leads me to the right answer: $x \in \{8k \pm 1 : 4|k \} = \{1, 31, 33, 63\}$
My question is whether there is a simpler way to do all of this; I can see it is true that for odd primes $p$ where $p \equiv 1 $ (mod 4) the solutions to $x^2 \equiv 1$ (mod $p^2$) are  $ x = \pm 1$ by a proof generalising my solution to (ii) but should that have been obvious?  This is a 6 mark question and I I'm sure there are shortcuts to be taken here. Is there some optimal way of seeing/ knowing that the solutions for $x^2 = 1$ (mod 8) are $\{\pm 1, \pm 3\}$ ?
I apologise, because I ended up answering most of my question while writing this, but still I do not regard my solutions as good solutions, and any superior methodology would be appreciated.
 A: I wouldn't immediately rule out brute force. And there might be some easier method using some of the theory behind quadratic residues (although I can't quite find an easy way to generate all solutions). However there is a fairly straightforward method using some variation on Hensel's Lemma. The gist of it is as follows:
Say $x^2 - 1$ has a root modulo $p^k$ at $x = r$, and we want to find the roots $s$ in $p^{k+d}$ (with $d \leq k$) that satisfy $s = r \mod p^k$, then those are of the form $(r + p^k t)$ and must satisfy
$$
0  =(r + p^k t)^2 - 1 = (r^2 - 1) + 2(r + p^k t) + p^{2k} \, (\textrm{higher order terms})
$$
Since $r^2 - 1 = 0 \mod p^k$ and $p^{k+d} | p^{2k}$ we find that $r^2 - 1 = z p^k$ for some $z$ and
$$
(r + p^k t)^2 - 1 = p^k (z + 2t) \mod p^{k+d}
$$
therefore a root must satisfy
$$
0 = (z + 2t) \mod p^{d}
$$
From this we can already conclude that if $p$ is odd then $2$ has an inverse modulo $p^d$ and the above equation has a unique solution for $t$, and since $x^2 + 1$ can have at most 2 solutions modulo some prime. This means that for any odd $p$ there are at most two solutions modulo $p^k$ for any $k$ (which must then be $1$ and $-1$).
Unfortunately that still leaves cases with $p = 2$. I wouldn't exactly rule out brute force for smaller powers, but we can use the formula to show that the only roots modulo $2^k$ are $\{\pm 1, \, 2^{k-1} \pm 1\}$ (note that this reduces to just one root when $k=1$).
To show this, assume it holds for roots modulo $2^{k-1}$. Then for the roots $r = \pm 1 \mod 2^{k-1}$ we find $s = (2^{k-1} t \pm 1)$ and $z=0$ and
$$
0 = 2 t \mod 2
$$
Which can be solved by $t = 0$ and $t = 1$. This results in the roots $\{\pm1,\, 2^{k-1} \pm 1\} \mod 64$. If $k\leq2$ this would be all roots, but assuming $k>2$ then for the roots $r = 2^{k-2} \pm 1 \mod 2^{k-1}$ we get that $(2^{k-2} - 1)^2 - 1 = 2^{k-1} (2^{k-3} + 1)$ hence $z = 1 \mod 2$ so $t$ must satisfy
$$
0 = (1 + 2t) \mod 2
$$
which has no solutions.
Hopefully this as least clarifies why the answers are what they are, even if trying to figure out the answers using these methods might not be the best strategy to get quick answers.
