El siguiente teorema se deja como ejercicio en K. Irlanda y M. Rosen es Un Clásico de Introducción a la Moderna Teoría de números. El teorema es la siguiente:
Deje $2^l$ ser la mayor potencia de 2 dividiendo $n$. Supongamos que $a$ es impar y que $x^n \equiv a \mod 2^{2l + 1}$ es solucionable. A continuación, $x^n \equiv a \mod 2^e$ tiene solución para todos los $e \geq 2l + 1$.
El texto dice que uno empieza por asumir que $x^n \equiv a \mod 2^m$ (para algunos $m \geq 2l + 1$) es solucionable y que $x_{0}$ es una solución de la congruencia. A continuación, $x_{1} = x_{0} + b2^{m - l}$ satisface $x_{1}^n \equiv a \mod 2^{m+1}$ para elegir adecuadamente un $b$.
Estoy particularmente interesado en el caso específico al $n = 2$, por lo que, a continuación, $l = 1$ y suponemos que $x^2 \equiv a \mod 2^m$ es solucionable, para algunos $m \geq 3$ $x_{0}$ una solución. Si dejamos $x_{0}^2 - a = 2^m k$ algunos $k \in \mathbb{Z}$ ($b$ aún por ser elegido) tenemos que $$x_{1}^2 - a = x_{0}^2 + 2^m b x_{0} + b^2 2^{2m - 2} - a = (x_{0}^2 - a) + 2^m b x_{0} + b^2 2^{2m - 2} = 2^m(k + bx_{0}) + b^2 \cdot 2^{2m - 2}$$
En este punto, tenía la esperanza de que sería evidente cómo debo seleccionar $b$, pero todavía no lo es. Desde $m \geq 3$,$2m - 2 \geq m + 1$$b^2 \cdot 2^{2m - 2} \equiv 0 \mod 2^{m + 1}$. Por lo tanto basta disponer de $k + bx_{0} = 2$ (o igual a alguna potencia de 2 mayor que 2).
Pensé que la selección de $b = 2x_{0} + k$ funcionaría, sin embargo, esto conduce a $$k + bx_{0} = k + (2x_{0} + k)x_{0} = k + 2x_{0}k + kx_{0}$$ y yo todavía incapaz de factor de 2 a partir de la expresión completa.
