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. 

This is equivalent to finding all $0\leq x \leq 255$ such that $256\mid x^2-9 $. But $256 = 2^8$ and $x^2-9 = (x-3)(x+3)$. But the greatest common divisor of $x-3$ and $x+3$ must divide $(x+3)-(x-3) = 6$. Hence, if $x+3$ is divisible by $4$, then $x-3$ is only divisible by $2$, and vice versa.
The statement is thus equivalent to finding $x$ such that $2^7 \mid x+3$ or $2^7\mid x-3$. Because $0\leq x \leq 255$ and $2^7 = 128$ there are four solutions:
$$\{3,128-3,128+3,256-3\} = \{3,125,131,253\}$$
