1
$\begingroup$

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

$\endgroup$

1 Answer 1

12
$\begingroup$

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?

$\endgroup$
3
  • 6
    $\begingroup$ Yes, it does make sense. Moreover, It is a special case of Hensel's lemma. $\endgroup$
    – user9072
    Nov 12, 2015 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, 2015 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, 2016 at 14:52

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