Raíces cuadradas modulo potencias de 2

Question

Experimentalmente, al parecer cada $a\equiv1\left(\bmod\,8\right)$ tiene 4 raíces cuadradas mod $2^n$ % todo $n \ge 3$(es decir soluciones a $x^2\equiv a\left(\bmod\,2^n\right)$)

¿Es esto cierto? Si es así, ¿cómo puedo demostrarlo? ¿Si no es menos cierto que el máximo (más $a$) número de raíces cuadradas de $a$mod $2^n$ está delimitado por un polinomio en $n$?

Answer 1

Al $n\ge 3$, el número de soluciones de $x^2\equiv 1\pmod{2^n}$$4$. Las soluciones se $x=\pm 1\pmod{2^n}$$x\equiv \pm 1+2^{n-1}\pmod{2^n}$.

Prueba: queremos $x^2-1\equiv 1\pmod{2^n}$, $(x-1)(x+1)\equiv 0\pmod{2^n}$. Desde $x$ debe ser impar, el mcd de a$x-1$$x+1$$2$. Todos los de la $2$'s vienen de $x-1$ o de todas las $2$'s vienen de $x+1$ o $n-1$ de ellos provienen de uno de los $x-1$ o $x+1$, e $1$ de ellos proviene de los otros.

Para conectar este con raíces cuadradas, tenga en cuenta que $u$ $v$ son las raíces cuadradas de los $a$, $uv^{-1}$ es una raíz cuadrada de $1$, y a la inversa. Así que si $a$ tiene una raíz cuadrada, se ha $4$ de ellos.

Para mostrar todos los $a$ congruente a $1$ mod $8$ tienen una raíz cuadrada, se utiliza un recuento de argumento. Tenga en cuenta que hay $2^{n-3}$ números entre el $1$ $2^n-1$ que son congruentes a $1$ modulo $8$, e $2^{n-1}$ números impares. Puesto que el cuadrado de la función es$4$$1$, debe ser el caso de que cada número congruente a $1$ modulo $8$ es la plaza de algo.

Answer 2

La ecuación modular $x^2\equiv1\pmod{2^n}$ puede escribirse así: %#% $ de #% es claro desde aquí que $$(x+1)(x-1)\equiv0\pmod{2^n}$ y $x+1$ son incluso. Puesto que la diferencia entre $x-1$y $x+1$ $x-1$, uno de estos números es un múltiplo de $2$ pero no de $2$. Esto implica que uno debe ser múltiples de $4$.

Esto da solamente cuatro posibilidades: $2^{n-1}$, $x\equiv1$, $x\equiv-1$ y $x\equiv2^{n-1}+1$, que son distintas porque $x\equiv2^{n-1}-1$ (estas congruencias son modulo $n\geq3$).

Answer 3

Si $n\ge3$ $a=8k+1$ $a$ tiene exactamente cuatro distintas raíces cuadradas modulo $2^n$.

La prueba de que existe al menos una raíz cuadrada: el uso de la inducción. El caso de $n=3$ es fácil de comprobar; si $x^2\equiv a\pmod{2^n}$ $x^2=a+2^nk$ para algunos entero $k$; es fácil ver que $x$ es impar y $$(x+2^{n-1}k)^2=a+2^nk(1+x)+2^{n+1}(k^22^{n-3})\equiv a\pmod{2^{n+1}}\ .$$

Encontrar todas las raíces cuadradas: desde $a\equiv x^2\pmod{2^n}$ necesitamos resolver $y^2=x^2\pmod{2^n}$. Esto le da $$2^n\mid (y-x)(y+x)\ .$$ Cada factor en el lado derecho es aún; pero no ambos son divisibles por $4$ como entonces su suma $2y$ sería un múltiplo de $4$, lo cual es imposible como $y$ es impar. Así tenemos $$2^{n-1}\mid y-x\quad\hbox{or}\quad 2^{n-1}\mid y+x\ .$$ Esto le da a las cuatro posibilidades $$y\equiv x\,,\ y\equiv x+2^{n-1}\,,\ y\equiv -x\,,\ y\equiv -x+2^{n-1}\pmod{2^n}\ ;$$ no es difícil comprobar que todos ellos son diferentes modulo $2^n$, y que de hecho son las raíces cuadradas de los $a$.