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 Humphries Nov 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?

  • 6
    $\begingroup$ Yes, it does make sense. Moreover, It is a special case of Hensel's lemma. $\endgroup$ – user9072 Nov 12 '15 at 18:55
  • $\begingroup$ Ah, thanks. I did have an approach like this one, but I wasn't analysing the linear congruence properly. $\endgroup$ – spliblib Nov 12 '15 at 19:01
  • $\begingroup$ 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)$. $\endgroup$ – bfhaha Aug 25 '16 at 14:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.