Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Experimentally, it seems like every $a\equiv1\left(\bmod\,8\right)$ has 4 square roots mod $2^n$ for all $n \ge 3$ (ie solutions to $x^2\equiv a\left(\bmod\,2^n\right)$)

Is this true? If so, how can I prove it? If not, is it at least true that the maximum (over $a$) number of square roots of $a$ mod $2^n$ is bounded by some polynomial in $n$?

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

When $n\ge 3$, the number of solutions of $x^2\equiv 1\pmod{2^n}$ is $4$. The solutions are $x=\pm 1\pmod{2^n}$ and $x\equiv \pm 1+2^{n-1}\pmod{2^n}$.

Proof: We want $x^2-1\equiv 1\pmod{2^n}$, that is, $(x-1)(x+1)\equiv 0\pmod{2^n}$. Since $x$ must be odd, the gcd of $x-1$ and $x+1$ is $2$. Either all of the $2$'s come from $x-1$, or all the $2$'s come from $x+1$, or $n-1$ of them come from one of $x-1$ or $x+1$, and $1$ of them comes from the other.

To connect this with square roots, note that $u$ and $v$ are square roots of $a$, then $uv^{-1}$ is a square root of $1$, and conversely. So if $a$ has a square root, it has $4$ of them.

To show all $a$ congruent to $1$ mod $8$ have a square root, we use a counting argument. Note that there are $2^{n-3}$ numbers between $1$ and $2^n-1$ that are congruent to $1$ modulo $8$, and $2^{n-1}$ odd numbers. Since the squaring function is $4$ to $1$, it must be the case that every number congruent to $1$ modulo $8$ is the square of something.

share|improve this answer
add comment

The modular equation $x^2\equiv1\pmod{2^n}$ can be written this way: $$(x+1)(x-1)\equiv0\pmod{2^n}$$ It is clear from here that $x+1$ and $x-1$ are even. Since the difference between $x+1$ and $x-1$ is $2$, one of these numbers is a multiple of $2$ but not of $4$. This implies that the other one must be multiple of $2^{n-1}$.

This gives only four possibilities: $x\equiv1$, $x\equiv-1$, $x\equiv2^{n-1}+1$ and $x\equiv2^{n-1}-1$, that are distinct because $n\geq3$ (all these congruences are modulo $2^n$).

share|improve this answer
add comment

If $n\ge3$ and $a=8k+1$ then $a$ has exactly four distinct square roots modulo $2^n$.

Proof that there is at least one square root: use induction. The case $n=3$ is easy to check; if $x^2\equiv a\pmod{2^n}$ then $x^2=a+2^nk$ for some integer $k$; it is easy to see that $x$ is odd and so $$(x+2^{n-1}k)^2=a+2^nk(1+x)+2^{n+1}(k^22^{n-3})\equiv a\pmod{2^{n+1}}\ .$$

Finding all square roots: since $a\equiv x^2\pmod{2^n}$ we need to solve $y^2=x^2\pmod{2^n}$. This gives $$2^n\mid (y-x)(y+x)\ .$$ Each factor on the RHS is even; but not both are divisible by $4$ as then their sum $2y$ would be a multiple of $4$, which is impossible as $y$ is odd. So we have $$2^{n-1}\mid y-x\quad\hbox{or}\quad 2^{n-1}\mid y+x\ .$$ This gives the four possibilities $$y\equiv x\,,\ y\equiv x+2^{n-1}\,,\ y\equiv -x\,,\ y\equiv -x+2^{n-1}\pmod{2^n}\ ;$$ it is not hard to check that they are all different modulo $2^n$, and that they are in fact square roots of $a$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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