Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

2 Answers 2

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|improve this answer
    
Thanks a lot, anon! –  MathNewbie Jul 1 '12 at 8:13
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.