Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Have a look at Hensel's lifting lemma. – hardmath Jul 1 '12 at 4:31
Solve $b^2 - a = px$ for $b^2$ and plug it in. – Hurkyl Jul 1 '12 at 5:10
up vote 5 down vote accepted

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$).

share|cite|improve this answer
Thanks a lot, anon! – MathNewbie Jul 1 '12 at 8:13

Generally, 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\:x_2 = x_1 - (x_1^2-a)/(2x_1)$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.