Could I get some help with this proof? It is supposed to be induction, but I have no idea where the $m \tilde {x_0} \frac 12 (p+1)p^k$ term near the bottom comes from. I understand how it is used for the inductive step but not how it was chosen.

$m p^k$ is familiar from the previous step but $\tilde {x_0} \frac 12 (p+1)$ seems to come out of the blue

  • 1
    $\begingroup$ If you have to include an image, please have the right side up. This is hard on my neck. $\endgroup$ – marty cohen Aug 11 '15 at 21:32
  • $\begingroup$ @martycohen apologies, I snapped the pic quickly on mobile $\endgroup$ – mysatellite Aug 11 '15 at 22:55

This is a good question: You can understand the proof line by line, but how could someone have thought to write that "magic" expression there?

First let's note that $\frac12(p+1)$ is the same as $2^{-1}$, the multiplicative inverse of $2$ modulo $p$. So the nominated root modulo $p^{k+1}$ is really $x_0 - (2x_0)^{-1}mp^k$ (using the definition of $\tilde x_0$).

Where does this come from? This is a special case of (the proof of) Hensel's lemma. In that derivation, you'll see that we have a root $r$ of $f(r)\equiv0\pmod{p^k}$, and we're trying to find a general formula for the number $t\pmod p$ such that $s=r+tp^k$ is a root of $f(s)\equiv0\pmod{p^{k+1}}$. The derivation shows that the general formula for $t$ is $t\equiv - \frac{f(r)}{p^k}f'(r)^{-1} \pmod p$, so that $s \equiv r - f(r)f'(r)^{-1}\pmod{p^{k+1}}$.

In our situation, $f(y)=y^2-a$ and $r=x_0$, so $f(x_0)$ is $x_0-a=mp^k$, while $f'(x_0)=2x_0$. Therefore $s=r+tp^k$ becomes $s=x_0-mp^k(2x_0)^{-1}$ - voila! That "magic" expression came from setting up an equation with an unknown variable $t$, solving for $t$, and then erasing all of the scratch work.

[Bonus fact: the formula $s \equiv r - f(r)f'(r)^{-1}\pmod{p^{k+1}}$ (which creates a root modulo $p^{k+1}$ out of a root modulo $p^k$) is exactly the same formula as in Newton's method (which yields a more accurate approximation to a root of a real-valued function!). And that leads to the relationship between the real numbers and the $p$-adic numbers....]

  • $\begingroup$ What a great answer! If only they left the scratch work for me to peruse ;D $\endgroup$ – mysatellite Aug 12 '15 at 13:01

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.