Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$. I need to find all the solutions of the congruence $x^2 \equiv 9 \mod 256$. 
I tried (apparently naively) to do this:
$x^2 \equiv 9 \mod 256$
   $\Leftrightarrow$      $x^2 -9 \equiv 0 \mod 256$  $\Leftrightarrow$ $256 | (x-3)(x+3)$ $\Leftrightarrow$
$256|(x-3)$ or  $256|(x+3)$  $\Leftrightarrow$ $x \equiv 3, -3 \mod 256$ 
but I found out that it's not fully correct because there are other solutions that I didn't succeed to find such as $x = 125$, so I want to know what is the general way to solve such questions? thank you!
 A: You can't reason from $256\mid ab$ to $256\mid a \lor 256\mid b$ because $256$ is not a prime. Instead you need to consider all the ways that the prime factors of $256$ can be distributed among $a$ and $b$.
Since $256$ is a prime power, namely $2^8$, there are only nine ways to write it as a product, and we can check those systematically:
Case 0. $256\mid(x-3)$ and $1\mid(x+3)$. This leads to the solution $x=3$.
Case 1. $128\mid(x-3)$ and $2\mid(x+3)$. The former implies the latter, so this leads to the solution $x=131$ as well as $x=3$ which we already know.
Case 2. $64\mid(x-3)$ and $4\mid(x+3)$. This would require the difference between $x-3$ and $x+3$ to be a multiple of $4$, which is never the case, so this is impossible.
Case 3. $32\mid(x-3)$ and $8\mid(x+3)$. Similar to case 2 -- impossible because $6$ is not a multiple of $8$.
Cases 4 through 6. Similar.
Case 7. $2\mid(x-3)$ and $128\mid(x+3)$. This gives $x=125$ or $x=253$.
Case 8. $1\mid(x-3)$ and $256\mid(x+3)$. This gives $x=253$, which we already know from case 7.
So the solutions are $\{3,125,131,253\}$.
A: You know that

$$(\Bbb Z/256\Bbb Z)^\times\cong \Bbb Z/2\Bbb Z \times \Bbb Z/64\Bbb Z$$

and Hensel's lemma gives a lifting for solutions if you can find them modulo $8$ and unique lifts. Since there are $4$ solutions modulo $8$, these lift to $4$ solutions modulo any higher power of $2$.
Edit: Since the op doesn't know Hensel, it's easy enough to just use the isomorphism directly, the square are index $4$, so if there is any square root, there are $4$ of them since any different ones differ by an element of the kernel of the squaring map.
A: If $(x-3)(x+3)\equiv0\pmod{2^{m+2}}$ for integer $m\ge1$
both $(x-3),(x+3)$ must be even
$\implies\dfrac{x-3}2\cdot\dfrac{x+3}2\equiv0\pmod{2^m}$
Now $\dfrac{x-3}2-\dfrac{x+3}2$ is odd  $\implies$ they have opposite parity
If $\dfrac{x-3}2$ is even, $\dfrac{x-3}2\equiv0\pmod{2^m},x\equiv3\pmod{2^{m+1}}$
Can you take it from here?
Here $m+2=8$ 
A: The obvious ones, $3^2 = 9$ and $(-3)^2 = 9.$
and $(128+3)^2 = 128^2 + 256 + 9\equiv 9\mod 256$
and $(128-3)^2 = 128^2 - 256 + 9\equiv 9\mod 256$
