Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

Question

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!

Answer 1

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

Answer 2

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.

Answer 3

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$