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
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....]