Relationship between quadratic residues modulo a prime and quadratic residues modulo a prime power [closed]

Been going through Alan Baker's A Comprehensive Course in Number Theory. Very interesting book, although the way proofs are presented sometimes throws me off a little.

I usually read through a chapter multiple times and then try and solve a few exercises (I can't say I'm proficient or smart enough to solve all of them). I wish the answers to some of the exercises were somewhere.

In any case, here's one that I've been struggling with, and I've found no simple proof (I think one is meant to only use the tools given in the chapter, which are Euler's criterion, Gauss' Lemma and the quadratic reciprocity law, both for Lagrange and for Jacobi symbols, or in previous chapters, such as generators):

Let $p$ be an odd prime and $a$ be an integer not divisible by $p$. Prove that, if $a$ is a quadratic residue $\bmod p$, then it is a quadratic residue $\bmod p^k$ for all positive integers $k$.

closed as off-topic by Ben Linowitz, Lucia, Qiaochu Yuan, Alexey Ustinov, Peter HumphriesNov 13 '15 at 5:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Ben Linowitz, Lucia, Qiaochu Yuan, Alexey Ustinov, Peter Humphries
If this question can be reworded to fit the rules in the help center, please edit the question.

I think a simple induction suffices. Suppose that $x^2\equiv a\pmod{p^k}$ with integer $x$ and $k$; that is, $x^2=a+tp^k$ where $t$ is also an integer. Then for any integer $n$, we have $(x+np^k)^2\equiv a+(t+2nx)p^k\pmod{p^{k+1}}$. Choosing $n$ to satisfy the linear congruence $t+2nx\equiv 0\pmod p$, we get $(x+np^k)^2\equiv a\pmod{p^{k+1}}$. Does this make sense, or have I got anything wrong?
• The existence of $n$ satisfying the linear congruence $t+2nx\equiv 0\pmod{p}$ follows from $(2x)n\equiv (-t)\pmod{p}$ is a linear Diophantine equation and $\gcd{(2x,p)}\mid (-t)$. – bfhaha Aug 25 '16 at 14:52