Prove that $x^2 \equiv a \pmod{p}$ has solution if and only if $x^2 \equiv a \pmod{p^e}$ has solution Problem

Prove that $x^2 \equiv a \pmod{p}$ has solution if and only if $x^2 \equiv a \pmod{p^e}$ has solution.

I attempted to prove this by induction, but I was struggling with the proving the converse.
If $x^2 \equiv a \pmod{p^{e+1}}$ then $x^2 = a + kp^{e+1}$. Hence, $x^2 \equiv a \pmod{p^e}$ is straightforward. However, the converse drove me nuts. 
By assuming that $x^2 \equiv a \pmod{p^e}$, then I have $x^2 = a + kp^e$, take this number modulo $p^{e+1}$, I can't see how this becomes $a \pmod{p^e}$. I used calculator to generate many cases to see how the pattern worked, and I realized the key idea is in $k$. But I couldn't figure out how to bring $k$ up from $p^e$ to $p^{e+1}$. Any idea?
Thank you   
 A: You need to lift one solution to the next power. See Hensel's lemma.
Here is how to lift one solution $u$ of $x^2 \equiv a \pmod p$ to a solution $v$ of $x^2 \equiv a \pmod {p^2}$: Write $u^2=a+kp$ for some $k$. Consider $v=u+tp$ with $t$ to be determined. Then $v^2 = u^2+2utp+p^2 = a+kp+2utp+p^2$. So we need $t$ such that $k \equiv 2ut \bmod p$. Assuming $p$ odd and  $a \not\equiv 0 \bmod p$, you can solve for $t$.
A: For $p=2$, the result is not true: taking $p=2$, $a=3$, $e^2$, we have that $x^2 \equiv 3\pmod{2}$ has a solution (any odd integer), but $x^2\equiv 3\pmod{2^2}$ has no solutions. 
If $\gcd(a,p)=p$ the result is also not necessarily true: take $a=p$; then $x^2\equiv p\pmod{p}$ has a solution, but $x^2\equiv p\pmod{p^2}$ does not, since $x$ would have to be a multiple of $p$, and hence $x^2\equiv 0\pmod{p^2}$.
If $a$ is restricted to lying in $\{0,1,\ldots,p-1\}$, then these two conditions don't matter: for $p=2$, it is clear that both $x^2\equiv 0\pmod{2^e}$ and $x^2\equiv 1\pmod{2^e}$ have solutions for all $e\gt 0$; and if $p$ is odd and $a=0$, then $x^2\equiv 0\pmod{p^e}$ has solutions for all $e\gt 0$.
So, in any case, we can restrict to the case where $p$ is odd and $\gcd(a,p)=1$. In particular, any solution to $x^2\equiv a\pmod{p}$ or to $x^2\equiv a \pmod{p^e}$  must be relatively prime to $p$. 
For odd primes, the problem can be solved using Hensel's Lemma, but one does not actually need it; just pushing it through what you are trying to do will do it, if you figure out what you need out of $k$ for things to work out.
Suppose $b^2 \equiv a \pmod{p^r}$, and you want to find $k$ such that $(b+kp^r)^2\equiv a \pmod{p^{r+1}}$. 
Doing simple squaring, you have
$$b^2 + 2bkp^r + k^2p^{2r}\equiv b^2 +2bkp^r \pmod{p^{r+1}}.$$
Now, $b^2 = a + tp^r$ for some $t$, so we want
$$tp^r + 2bkp^r = p^r(t+2bk)\equiv 0 \pmod{p^{r+1}}.$$
This is equivalent to asking that
$$t + 2bk\equiv 0 \pmod{p}.$$
So pick $k$ with $k(2b) \equiv -t\pmod{p}$ (which can be done because both $b$ and $2$ are relatively prime to $p$), and we are done.
By the way: one way to think of Hensel's Lemma is that it is the modular version of Newton's Method for approximating roots.  
In Newton's Method, if $f'(b)\neq 0$, then you can go from $b$ to $b - \frac{f(b)}{f'(b)}$ as the "next approximation". Hensel's Lemma works the same way: you need $f'(b)$ to not be zero modulo $p$. Here we are working with $f(x) = x^2-a$; as long as $p\neq 2$, the formal derivative is not identically zero, which suggests what to do.
Notice the similarity with Newton's method in what we did: if $f(x) = x^2 - a$, then $f'(x)=2x$, so $f'(b)=2b$, and $f(b) = b^2-a = tp^r$, so
$$ b - \frac{f(b)}{f'(b)} = b - \frac{tp^r}{2b} = b + \left(\frac{-t}{2b}\right)p^r$$
and what we are going to do is take $b+kp^r$ with $k$ given by
$$k(2b)\equiv -t\pmod{p};$$
that is, $k$ is congruent to $\frac{-t}{2b}$ modulo $p$; precisely $-\frac{f(b)}{f'(b)}$ modulo $p$.
