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 four solutions are $\pm3$ and $\pm125$. – Lucian May 25 '15 at 9:23

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\}$$

Notice that $(16)^2=256$, so squaring $16k+r$ cancels $k^2$ term, so we're motivated to start with mod $16$ and then substitute $x=16k+r$ and find $k$ mod $256$.

$x^2\equiv 9\pmod{\! 16}\,\Rightarrow\, x\equiv \pm 3,\pm 5$ by checking all $\{\pm 1,\pm 3,\pm 5,\pm 7\}$. Two cases:

$1)$ $\, x=16k\pm 3\,\Rightarrow\, (16k\pm 3)^2\equiv 256k^2\pm 96k+9\equiv 9\pmod{\! 256}$

$\iff \pm 96k\equiv 0\pmod{\! 256}\stackrel{(256,96)=32}\iff k\equiv 0\pmod{\!8}\iff k=8n$

So $x^2\equiv 9\pmod{\! 256}$ is satisfied iff (i.e. $\!\!\iff\!$) $x=128n\pm 3$ in this case.

$2)$ $\, x=16k\pm 5\,\Rightarrow\, (16k\pm 5)^2\equiv 256k^2\pm 160k+25\equiv 9\pmod{\! 256}$

$\iff \pm 160k\equiv -16\pmod{\! 256}\iff \pm 160k+256l+16=0$, impossible mod $32$.

$1$st case gives $x\equiv \{\pm 3,\pm 125\}\pmod{\! 256}$, $2$nd case gives no solutions.

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