Hensel elevando raíces cuadradas $\!\bmod p\,$ a $\!\bmod p^2$

Question

He estado trabajando en este problema por un tiempo, pero llegué a un callejón sin salida.

Aquí está el problema:

Supongamos que $p$ es un número primo impar. También sea $b^2 \equiv a \pmod p$ y $p$ no divide a $a$. Demuestra que existe algún $k \in \mathbb{Z}$ tal que $(b+kp)^2 \equiv a \pmod {p^2}.

Esto es lo que he intentado hasta ahora:

$$ (b+kp)^2 \equiv b^2 + 2bkp + k^2p^2 \equiv a \pmod {p^2}$$

Aquí, necesito encontrar un $k$ que satisfaga esta congruencia. Equivalentemente, necesito encontrar $k$ tal que $p^2$ divida $(b^2-a) + 2bkp + p^2k^2$ o equivalentemente mostrar que $p^2$ divide $(b^2-a) + 2bkp$ para algún $k \in \mathbb{Z$}.

Hasta ahora, como $p$ divide a $(b^2-a)$, entonces por definición, existe algún $x \in \mathbb{Z}$ tal que $b^2-a = px$. Me quedé atascado aquí, he intentado algunos ejemplos, pero no he visto ningún patrón que se refiera a este problema.

Cualquier idea sería útil.

Answer 1

Buscas un $k$ tal que $p^2\mid \big((b^2-a)+2kbp\big)$. Ahora, $b^2-a$ ya es un múltiplo de $p$, digamos $\ell p$. Nota que $uv\mid uw\iff v\mid w$, por lo que deducimos (usando $u=v=p$) que $$p^2\mid \big((b^2-a)+2kbp\big)\iff p\mid (\ell+2bk)\iff \ell+2bk\equiv0 \bmod p.$$

Dado que $p$ es impar y $p\not\mid b$, puedes resolver para $k$ usando aritmética modular ($2b$ es invertible módulo $p$).

Answer 2

En general, como aquí, suponga $\rm\:f(x) \in \mathbb Z[x]\:$ y $\rm\:f(x_1)\equiv 0\pmod p.\,$

Por Taylor, $\rm\ 0\equiv f(x_1\!+kp) \equiv f(x_1) + f'(x_1)\, kp \pmod{p^2}$

$\rm\qquad \iff p^2\:|\:p\,(f(x_1)/p + f'(x_1)k)\iff p\:|\:f(x_1)/p + f'(x_1)\, k$

Si $\rm\: p\nmid f'(x_1)\:$ esto tiene una solución única $\rm\ k \equiv -f(x_1)/(p\, f'(x_1))\pmod p\:$

Por lo tanto $\rm\:f(x_2)\equiv 0\pmod{p^2}\:$ para $\rm\:x_2 = x_1\! + kp \equiv x_1 - \dfrac{f(x_1)}{f'(x_1)}\pmod p$

Si conoces cálculo, es posible que reconozcas esto como el método de Newton (aquí llamado Lema de Hensel).

En tu caso $\rm\:f(x) = x^2\! - a,\:$ así que $\rm\:f'(x) = 2x,\:$ por lo que $\rm\:\bbox[5px,border:1px solid #c00]{x_2 = x_1 - (x_1^2-a)/(2x_1)}$