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$.
> 
> 
> 



Relationship between quadratic residues modulo a prime and quadratic residues modulo a prime power
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?


