Let $a$ be an odd integer. Show that the congruence $x^2 \equiv a \pmod {2^e}$, where $e$ is an integer, $e \geq 3$, has either no solutions or exactly 4 incongruent solutions.


closed as off-topic by TMM, Old John, Thomas Andrews, Branimir Ćaćić, Dan Rust Jan 5 '14 at 16:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TMM, Old John, Thomas Andrews, Branimir Ćaćić, Dan Rust
If this question can be reworded to fit the rules in the help center, please edit the question.


If $x^2\equiv a\pmod{2^e}$ the also $x^2\equiv a\pmod{8}$. A square is odd iff the number itself is odd, and the square of an odd number is always $\equiv1\pmod 8$. Therefore, there is no solution if $a\not\equiv 1\pmod 8$. On the other hand, if $a\equiv 1\pmod 8$ there are exactly four solutions. This can be shown by induction on $e$. Indeed, if $e=3$, then $1,3,5,7\bmod 8$ are the four soulutions. Assume we have exactly four soulutions $x_1, x_2, x_3, x_4$ modulo $2^e$. Then there are at most eight solutions modulo $2^{e+1}$, namely $x_1, x_2, x_3, x_4, x_1+2^e, x_2+2^e, x_3+2^e, x_4+2^e$. But $$(x_i+2^e)^2=x_i^2+2^{e+1}x_i+2^{2e}\equiv x_i^2+2^{e+1}\pmod{2^{e+1}}$$ because $x_i$ is odd, so that of each pair $x_i, x_i+2^e$ there is at most one solution modulo $2^{e+1}$. On the other hand, $x_i^2\equiv a\pmod {2^e}$ implies that $x_i^2\equiv a\pmod {2^{e+1}}$ or $x_i^2\equiv a+2^e\pmod {2^{e+1}}$ so that eihter $x_i$ or $x_i+e^2$ gives us a solution modulo $2^{e+1}$.

  • 1
    $\begingroup$ Why are there at most $8$ solutions? How does your argument show that only one of each pair is a solution? $\endgroup$ – chubakueno Jan 5 '14 at 19:50
  • 2
    $\begingroup$ It looks to me that it shows that if $x$ is a solution, then so is $x+2^e$ $\endgroup$ – chubakueno Jan 5 '14 at 20:04

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