Show that $x^2\equiv a \pmod {2^n}$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$

Show that $$x^2\equiv a \pmod {2^n}$$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$

Actually, the question I had to solve was more complicated something like this:

$x^2\equiv a \pmod{2^n}$ has a solution where $n \ge3$ iff $a\equiv1 \pmod 8$ and the equation has exactly 4 incongruent solutions.

I figured out every other things. First, when the equation do have a solution, then $a\equiv1 \pmod{8}$ and the equation has exactly 4 incongruent solutions. The problem is that I couldn't prove that the equation do have at least one solution when $a\equiv1 \pmod{8}$, which is the reverse part of the proof. That is the only remaining part of my proof.

Could anybody fill in the missing part of my proof? Thanks in advance.

(The hard part of this problem for me was that I couldn't use Legendre symbols or primitive roots something like that since it is about $\pmod {2^n}$.)

• johndcook.com/quadratic_congruences.html – lab bhattacharjee Nov 8 '13 at 3:25
• @lab bhattacharjee Thanks my friend. That was really helpful. Now what I wonder now is what if $(a, m)\not=1$ in the reference. I.e., what if we consider when a is even in this case? Because obviously when a=4, it does have a solution. I actually tried to tackle that problem(find conditions for the equation to have a solution when a is even, too), but I failed. – Taxxi Nov 8 '13 at 4:10