Demostrar que$x^2 \equiv a \pmod{p}$ tiene solución si y sólo si$x^2 \equiv a \pmod{p^e}$ tiene solución

Question

Problema

Demostrar que $x^2 \equiv a \pmod{p}$ tiene solución si y sólo si $x^2 \equiv a \pmod{p^e}$ tiene solución.

He tratado de demostrar mediante la inducción, pero yo estaba luchando con la prueba a la inversa.
Si $x^2 \equiv a \pmod{p^{e+1}}$$x^2 = a + kp^{e+1}$. Por lo tanto, $x^2 \equiv a \pmod{p^e}$ es sencillo. Sin embargo, a la inversa me volvía loco. Suponiendo que $x^2 \equiv a \pmod{p^e}$, entonces he a $x^2 = a + kp^e$, tome este número modulo $p^{e+1}$, yo no puedo ver cómo esto se convierte en $a \pmod{p^e}$. He usado la calculadora para generar muchos casos para ver cómo el patrón se teje, y me di cuenta de que la idea clave es la de $k$. Pero yo no podía entender cómo llevar a $k$$p^e$$p^{e+1}$. Alguna idea?

Gracias

Answer 1

Es necesario levantar una solución a la siguiente potencia. Ver el lema de Hensel .

Aquí es cómo levantar una solución$u$ de$x^2 \equiv a \pmod p$ a una solución$v$ de$x^2 \equiv a \pmod {p^2}$: Escribir$u^2=a+kp$ para algunos$k$. Considere$v=u+tp$ con$t$ a determinarse. Entonces $v^2 = u^2+2utp+p^2 = a+kp+2utp+p^2$. Así que necesitamos$t$% tal que $k \equiv 2ut \bmod p$. Suponiendo$p$ impar y$a \not\equiv 0 \bmod p$, puede resolver para$t$.

Answer 2

Para $p=2$, el resultado no es cierto: tomar $p=2$, $a=3$, $e^2$, tenemos que $x^2 \equiv 3\pmod{2}$ tiene una solución (cualquier entero impar), sino $x^2\equiv 3\pmod{2^2}$ no tiene soluciones.

Si $\gcd(a,p)=p$ el resultado tampoco es necesariamente cierto: tome $a=p$; a continuación, $x^2\equiv p\pmod{p}$ tiene una solución, sino $x^2\equiv p\pmod{p^2}$ no, ya $x$ tendría que ser un múltiplo de $p$, y, por tanto,$x^2\equiv 0\pmod{p^2}$.

Si $a$ está restringido a la mentira en $\{0,1,\ldots,p-1\}$, entonces estas dos condiciones no importa: para $p=2$, es evidente que tanto la $x^2\equiv 0\pmod{2^e}$ $x^2\equiv 1\pmod{2^e}$ tienen soluciones para todos los $e\gt 0$; y si $p$ es impar y $a=0$, $x^2\equiv 0\pmod{p^e}$ tiene soluciones para todos los $e\gt 0$.

Así que, en cualquier caso, se puede restringir a los casos en que $p$ es impar y $\gcd(a,p)=1$. En particular, cualquier solución a $x^2\equiv a\pmod{p}$ o a $x^2\equiv a \pmod{p^e}$ debe ser relativamente primer a $p$.

Para los impares, números primos, el problema puede ser resuelto mediante la Hensel del Lema, pero uno realmente no necesita, empujando a través de lo que usted está tratando de hacer va a hacer, si usted averiguar lo que usted necesita de $k$ para que las cosas funcionen.

Supongamos $b^2 \equiv a \pmod{p^r}$, y quieres encontrar a $k$ tal que $(b+kp^r)^2\equiv a \pmod{p^{r+1}}$.

Hacer un simple cuadrado, tiene $$b^2 + 2bkp^r + k^2p^{2r}\equiv b^2 +2bkp^r \pmod{p^{r+1}}.$$ Ahora, $b^2 = a + tp^r$ algunos $t$, por lo que queremos $$tp^r + 2bkp^r = p^r(t+2bk)\equiv 0 \pmod{p^{r+1}}.$$ Esto es equivalente a pedir que $$t + 2bk\equiv 0 \pmod{p}.$$

Así que elija $k$ $k(2b) \equiv -t\pmod{p}$ (que puede ser hecho, porque tanto $b$ $2$ son relativamente primos a $p$), y hemos terminado.

Por cierto: una manera de pensar de Hensel del Lexema es que es el sistema modular de la versión del Método de Newton para aproximar las raíces.

En el Método de Newton, si $f'(b)\neq 0$, entonces usted puede ir de $b$ $b - \frac{f(b)}{f'(b)}$como la "nueva aproximación". Hensel del Lema funciona de la misma manera: se necesita $f'(b)$ a no ser cero modulo $p$. Aquí estamos trabajando con $f(x) = x^2-a$;$p\neq 2$, la formal derivado no es idéntica a cero, lo que sugiere qué hacer.

Cuenta de la similitud con el método de Newton en lo que hicimos: si $f(x) = x^2 - a$,$f'(x)=2x$, lo $f'(b)=2b$, e $f(b) = b^2-a = tp^r$, por lo que $$ b - \frac{f(b)}{f'(b)} = b - \frac{tp^r}{2b} = b + \left(\frac{-t}{2b}\right)p^r$$ y lo que vamos a hacer es tomar $b+kp^r$ $k$ dada por $$k(2b)\equiv -t\pmod{p};$$ es decir, $k$ es congruente a $\frac{-t}{2b}$ modulo $p$; precisamente, $-\frac{f(b)}{f'(b)}$ modulo $p$.