Finding the solutions of $x^2\equiv 9 \pmod {256}$. Find the solutions of $x^2\equiv 9 \pmod {256}$. I try to follow an algorithm shown us in class, but I am having troubles doing so. First I have to check how many solutions there are. Since $9\equiv 1 \pmod {2^{\min\{3,k\}}}$ where k fulfills $256=2^k$, then since $k\ge 3$, there are 4 solutions. 
As I understood, I have to take a smaller power of 2 and check $x^2\equiv 1 \pmod{2^m}$. I took m=4 and found that x=5 is a solution. According to the algorithm, I should take $x=5+Ax$ where A is a power of 2 and raise it by 2 and check congruence modulo, 256(I guess?), but the examples I were given didn't tell me accurately what I am to pick. I could really use your help on this. 

The answers above explain the idea great. If you need a general Formula 
for solving all the questions of this type then check this out -
$x^2 \equiv a \pmod {2^n}$ where a is odd
for n = 1 there is one answer and it is $x \equiv 1$
for $n = 2$ then we separate for 2 cases - 
$ a \equiv 1$ then we have two answers $x \equiv 1,3$
$a \equiv 3$ then we have no solution
now, in your case when $n \ge 3$ , and $a \equiv 1 \pmod 8$ we always have 4 solutions.
all you need to do is find one  easy solution - lets call it $x_0$
in your case $(x-3)(x+3) \equiv 0 \pmod {256}$ 
so lets pick $x_0 = 3$ as our easy solution.
Then all 4 solutions are - 
$x_0 , -x_0, x_0 + 2^{n-1} , -x_0 + 2^{n-1}$
which gives the answers as above ${3,125,131,253 \equiv -3}$
write if you need proof for the above
