Solve $x^2\equiv a$ mod $p$ Suppose $x_0$ solves  $x^2 \equiv a$ mod $p$, where $p$ is a prime. Then $x_0$ solves  $x^2 \equiv a$ mod $p^i$ for $i\geq1$. My question is: Is there a general way to find all the solutions to $x^2 \equiv a$ mod $p^i$ given the solutions of $x^2 \equiv a$ mod $p$?
 A: First, you stated the result backwards:
If $x_0$ solves $x^2=a \pmod{p^i}$ then $x_0$ solves $x^2 = a \pmod{p}$. 
To go backwards, which is what you want, you have to use the Hensel's Lemma . Hensell's lemma tells you that when you know a solution of $x^2=a \pmod{p}$, when a solution to $x^2=a \pmod{p^i}$ exists and how to get ALL the solutions which correspond to $x^2=a \pmod{p}$ (it actually workds for any polynomial).
For the equation you have, the Hensel Lemma tells you that when $p \neq 2$ and $a \neq 0$, there exists exactly one solution corresponding to $x_0$ for each $p^i$, and that things are a bit trickier when $p=2$ and/or $a=0$.
A: First of all your comment is wrong , for example $7^2 = 15 \mod 17$ but $7^2 \not= 15 \mod 17^2 $ or $17^3$ and so on.
Secondly yes you can find all the solutions to $x^2 = a \mod p^i$ using Tonelli–Shanks algorithm with extra change to the algorithm that is instead of taking $p-1 = Q 2^s$ you will find $Q ,s$ such that $p^{i-1} (p-1) = Q 2^s$ because $\phi(p) = p-1$ and $\phi(p^i)= p^{i-1} (p-1)$.
note : i am not sure but i think with other modifications to the algorithm you can even solve $x^j = a \mod p^i$ (again i am not sure).
also this algorithm work for prime and prime power because they have explicit Euler phi formula but it will not work with composite numbers.
