4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Have a look at Hensel's lifting lemma. $\endgroup$ – hardmath Jul 1 '12 at 4:31
  • $\begingroup$ Solve $b^2 - a = px$ for $b^2$ and plug it in. $\endgroup$ – user14972 Jul 1 '12 at 5:10
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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