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