<s>[INST] solving $x^2 = a \pmod {2^n}$ , $n \ge 3$ I read that the equation $x^2 = a \pmod {2^n}$ for $n \ge 3$ has four solutions and the solutions are $x_1, -x_1, x_1 + 2^{n-1}, - x_1 + 2^{n-1}$. It is easy to prove that they are indeed the solutions and are incongruent solutions. But if I need to derive that these are the only four solutions then how do I proceed?
Thanks
 [/INST] We need to assume that $a$ is odd. For example, if $a=4$, modulo $32$ we have solutions $2,6,10,14,18,22,26,30$. 
Suppose that $x_1^2\equiv a \pmod{2^n}$ and $x\equiv a\pmod{2^n}$. We need to show that $x$ can take on at most $4$ values.
From the two congruences, we have $x^2\equiv x_1^2\pmod{2^n}$, meaning that 
$2^n$ divides $(x-x_1)(x+x_1)$. 
Note that $x$ and $x_1$ are both odd. This implies that one of $x-x_1$ or $x+x_1$ is congruent to $2$ modulo $4$. The other therefore must be divisible by $2^{n-1}$. If you need details here, either $x\equiv x_1\pmod{4}$, in which case $x+x_1\equiv 2\pmod{4}$, or $x\equiv -x_1\pmod{4}$, in which case $x-x_1\equiv 2\pmod{4}$.
A little play then gives us the desired result. Perhaps $2^n$ divides $x-x_1$, giving the solution $x\equiv x_1$. Perhaps $2^n$ divides $x+x_1$, giving solution $x\equiv -x_1\pmod{2^n}$.
If neither of these cases holds, then because one of $x_1-x_2$ and $x+1+X_2$ contributes pnly one $2$, the other must contribute exactly $n-1$. 
Suppose the highest power of $2$ that divides $x-x_1$ is $2^{n-1}$. Then $x\equiv x_1+2^{n-1}\pmod{2^n}$.  
Suppose that the highest power of $2$ that divides $x+x_1$ is $2^{n-1}$. Then $x\equiv -x_1+2^{n-1}\pmod{2^n}$. 
The cases are not distinct if $n\lt 3$, but we do not need that to show there are at most $4$ solutions.  
</s>