Prove that Quadratic Residual $\mod p \rightarrow$ Quadratic Residual $\mod p^n$ 
Suppose that $x^2 = a \mod p$ has a solution.  Show that $x^2 = a \mod p^n$ has a solution.

Write $p, p^n$ into products of prime power, say $p = \prod_{i=1}^s q_i^{r_i}$ and $p^n = \prod_{i=1}^s q_i^{nr_i}$.  Because $p | x^2 - a$ if and only if $q_i^{r_i} | x^2 - a$ for each $i \in \{ \, 1, 2 \ldots s \, \}$, we can take $p$ to be a prime power, say $q = q^r$.  It follows that $q | x^2 - a$.  So, there is no loss of generality in assuming that $p$ is prime.
After many trials and errors, this is what I came up with:
\begin{eqnarray*}
(x^2 - a)^{p^n} & = &\sum_{k=0}^{p^n} \binom{p^n}{k} (x^2)^{p^n-k}(-a)^k \\
& = & (x^2)^{p^n} + (-a)^{p^n} \\
& = & (x^2)^{p^n} - a^{p^n} \\
& = & (x^2 - a)Q(x^2, a) & = & 0 \mod p^n
\end{eqnarray*}
I know that the proof is WRONG because the middle terms are not always divisible by $p^n$.  My question is how do I find the appropriate exponent for the middle terms to disappear?
 A: If $p$ is an odd prime, $a\in\mathbb Z$, $p\nmid a$, then if $x^2\equiv a\pmod{p}$ is solvable, then $x^2\equiv a\pmod{p^n}$ is solvable for all $n\in\mathbb Z^+$.
(some counterexamples if $p=2$ or $p\mid a$: $x^2\equiv 3\pmod{2}$ is solvable, $x^2\equiv 3\pmod{4}$ is not. $x^2\equiv 3\pmod{3}$ is solvable, $x^2\equiv 3\pmod{9}$ is not).
Proof: Hint: see Modular Inverse, notice $\gcd(2x,p)=1$ and
$$(x^2-a)^2=(x^2+a)^2-a(2x)^2$$
A: Suppose that $p$ is an odd prime that does not divide $a$, and we have found a solution $c$ of $x^2\equiv a\pmod{p^k}$.  We show how to lift the solution to a solution of $x^2\equiv a\pmod{p^{k+1}}$. Look for a solution of the form $x=c+tp^k$. 
Squaring we obtain $c^2+2ctp^k+t^2p^{2k}\equiv a\pmod{p^2}$. So we want
$$2tp^k\equiv a-c^2\pmod{p^{k+1}}.$$  But we know that $a-c^2$ is divisible by $p^k$. Say it is $dp^k$. The dividing both sides by $p^k$, we find that we want 
$$2ct\equiv d\pmod{p}.\tag{1}$$
Since $p$ is odd, we have $2c\not\equiv 0\pmod{p}$. It follows that the congruence (1) has a solution $t$. Thus from a solution mod $p^k$ we have produced a solution mod $p^{k+1}$. Finally, we work our way from $k=1$ all the way to $n$.  
Remark: For more detail, please look under Hensel lifting.
