Hensel lifting square roots $\!\bmod p\,$ to $\!\bmod p^2$

Question

I've been working on this problem for a while, but hit a dead end.

Here's the problem:

Suppose $p$ is an odd prime. Also let $b^2 \equiv a \pmod p$ and $p$ does not divide $a$. Prove there exists some $k \in \mathbb{Z}$ such that $(b+kp)^2 \equiv a \pmod {p^2}$.

Here's what I've tried so far:

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

Here, I need to find such $k$ that satisfy this congruence. Equivalently, I need to find such $k$ so that $p^2$ divides $(b^2-a) + 2bkp + p^2k^2$ or equivalently show that $p^2$ divides $(b^2-a) + 2bkp$ for some $k \in \mathbb{Z}$.

So far, since $p$ divides $(b^2-a)$, then by definition, there exists some $x \in \mathbb{Z}$ such that $b^2-a = px$. I got stuck here, and I've tried some examples, but I haven't seen any pattern that pertains to this problem.

Any insight would be helpful.

Answer 1

You seek a $k$ such that $p^2\mid \big((b^2-a)+2kbp\big)$. Now, $b^2-a$ is already a multiple of $p$, say $\ell p$. Note that $uv\mid uw\iff v\mid w$, so we deduce (using $u=v=p$) that $$p^2\mid \big((b^2-a)+2kbp\big)\iff p\mid (\ell+2bk)\iff \ell+2bk\equiv0 \bmod p.$$

Since $p$ is odd and $p\not\mid b$, you can solve for $k$ using modular arithmetic ($2b$ is invertible modulo $p$).

Answer 2

Generally, as here, suppose $\rm\:f(x) \in \mathbb Z[x]\:$ and $\rm\:f(x_1)\equiv 0\pmod p.\,$

By 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$

If $\rm\: p\nmid f'(x_1)\:$ this has a unique solution $\rm\ k \equiv -f(x_1)/(p\, f'(x_1))\pmod p\:$

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

If you know calculus you may recognize this as Newton's method (here called Hensel's Lemma).

In your case $\rm\:f(x) = x^2\! - a,\:$ so $\rm\:f'(x) = 2x,\:$ so $\rm\:\bbox[5px,border:1px solid #c00]{x_2 = x_1 - (x_1^2-a)/(2x_1)}$