Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$. Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then  $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$.
I have solved the first part but second part need help.
my solution for first is
If $p$ is odd and $(x^2)-a=0$ (mod $p)$ has a solution $b$, then
$(x^2)-a=(x^2)-b^2=(x-b)(x+b)=0$ (mod $p$)
$⇔x=b $(mod $p$) or $x=-b ($mod $p)$
So, it has a solution.
 A: I just could not make out your method.
If I've understood the question:
Let $x^2\equiv a\pmod{p^k}\iff$ there exist integer $u,c$ such that $$u^2=a+cp^k$$
If $p|c, u^2\equiv a\pmod{p^{k+1}}$ and we are done
Otherwise $(p,c)=1, (u+dp^k)^2=u^2+d^2p^{2k}+2udp^k\equiv a+p^k(c+2ud)\pmod{p^{k+1}}$ for $2k\ge k+1\iff k\ge1$
As $(cu,p)=1$ we can find integer $d$ such that $p|(c+2ud);$ consequently $u+dp^k$ is a solution of $$x^2\equiv a\pmod{p^{k+1}}$$
A: Suppose that $b^2\equiv a\bmod p$. Then $b^2=a+mp$ for some $m\in\Bbb Z$.
Let $\beta=b+kp$. Obviously $\beta\equiv b\bmod p$. Now write
$$
\beta^2=(b+kp)^2=b^2+2bkp+k^2p^2\equiv a+(m+2k)p\bmod p^2
$$
Since $p$ is odd, the congruence $2k+m\equiv 0\bmod p$ can always be solved. For the value of $k$ solving this congruence, we get from the displayed line above
$$
\beta^2\equiv a\bmod p^2.
$$
So, you constructed a solution modulo $p^2$.
Now suppose that you have constructed a solution $\beta_n$ for the congruence modulo $p^n$. Using the very same technique you can construct a solution of the congruence modulo $p^{n+1}$ of the form $\beta_{n+1}=\beta_n+kp^n$.
Thus, there is a solution of the congruence modulo every power of $p$

(lab bhattacharjee was quicker!)
