3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The four solutions are $\pm3$ and $\pm125$. $\endgroup$ – Lucian May 25 '15 at 9:23
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.