Square roots in the $p$-adics

Suppose $(n,p) = 1$ and $n$ is a square mod $p$, so the square root in ${\mathbb Q}_p$ should exist. One quick way to explicitly find good approximations of it is Newton's method. The iteration is $x_{k+1} = \frac{x_k + n/x_k}{2}$ where $x_0$ is an integer with $n \equiv x_0^2 \mod p$. Then $x_{k+1}^2 - n = (x_k - n)^2/4$ so $\|x_{k+1}^2 - n\|_p = \|x_k^2 - n\|_p^2$. Since $\|x_0^2 - n\|_p \le p^{-1}$ we get $\|x_k^2 - n\|_p \le p^{-2^k}$. For example, with $n=5$ and $p=11$, taking $x_0 = 4$ we have $x_1 = (4 + 5/4)/2 = 21/8 = 4 + 4 \cdot 11 + O(11^2)$, $x_2 = 761/336 = 4 + 4 \cdot 11 + 10 \cdot 11^2 + 4 \cdot 11^3 + O(11^4)$, $x_3 = 1143601/511392 = 4 + 4 \cdot 11 + 10 \cdot 11^2 + 4 \cdot 11^3 + 9 \cdot 11^5 + 5 \cdot 11^6 + 8 \cdot 11^7 + O(11^8)$, etc.

Yes, this is a direct application of Hensel's lemma.

By definition, ${\sqrt q} \in \mathbf{Z}_p$, if and only if the polynomial $f(x)=x^2-q$ splits in $\mathbf{Z}_p$.

In particular, $f$ must have a root $\alpha$ mod $p$, which is a quadratic residue of $p$. It cannot be a double root because $f'(x)=2x$ and $p\neq 2$, $\alpha\neq 0$. Hence by Hensel's lemma, $\alpha$ lifts to a root $\alpha'$ of $f$ in $\mathbf{Z}_p$. Thus the primes which split in $\mathbf{Z}_p$ are the quadratic residues of $p$.

I'll let you determine for general $n$... :-)