Prove that if $a$ where $0 \leq a < p^n$ is a quadratic residue modulo $p^n$ where $p$ is a prime, then $a$ is a quadratic residue modulo $p^{n+1}$.

I thought about trying to construct the residues from previous residues. For example, modulo $2^4$ we have $0,1,4,9$ to be the quadratic residues. The quadratic residues modulo $2^5$ are $0,1,4,9,16,17,25$ and so on.

  • $\begingroup$ what do you mean? is $a$ an integer suuch that its residue class mod $p^n$ is a quadratic residue? $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:37
  • $\begingroup$ @JorgeFernándezHidalgo Yes, that's right. $\endgroup$ – Puzzled417 Jan 9 '17 at 4:38
  • $\begingroup$ This is false. 7 is a quadratic residue mod 5 but not 25. $\endgroup$ – mathworker21 Jan 9 '17 at 4:40
  • 1
    $\begingroup$ $7$ is not a quadratic residue $\bmod 5$ $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:43
  • 1
    $\begingroup$ I'm sure this has been adequately covered earlier. See here and here or here for closely related discussion. Somehow the previous askers managed to make their question hide the search engine :-) $\endgroup$ – Jyrki Lahtonen Jan 9 '17 at 7:12

Let $x^2=a+kp^n$ where $a$ is an integer

Case $\#1:$ If $a=0, x$ must be divisible by $\left\lceil\dfrac n2\right\rceil$

So if $n=2m,$ the highest power of $p$ that divides $x,$ can be $m$

In that case $p^{n+1}=p^{2m+1}$ can not divide $x$

Case $\#2:$

If $p\mid k,$ we are done.

Else $p\nmid k\iff(k,p)=1$

For some integer $m,p\nmid m\iff(m,p)=1$

$(x+mp^n)^2=x^2+2x\cdot mp^n+(mp^n)^2$

$=a+p^n(k+2x\cdot m)+(mp^n)^2\equiv a+p^n(k+2x\cdot m)\pmod{p^{n+1}}$

We need $k+2x\cdot m\equiv0\pmod p$

As $(kx,p)=1,$ we can always find $m$ by Bézout's Lemma


In the case in which $p\nmid a$ then it is only false when $a=2$ and $n=1$.

The proof is easy if you know that the structure of the multiplicative group $\bmod p^n$ is as follows:

$\mathbb Z_{p^n-1}\times \mathbb Z_p$ if $p$ is an odd prime and $\mathbb Z_{2^{n-2}} \times \mathbb Z_2$ for $p=2$-

So as you can see the number of quadratic residues is exactly half in the first case and exactly one fourth in the second case. since each residue class $\bmod p^n$ gives us exactly $p$ residue classes $\bmod p^{n+1}$ we conclude that a residue class $\bmod p^{n+1}$ is a quadratic residue if and only if its respective class $\bmod p^n$ is a quadratic residue.

Notice that the result is not true if $p|a$, because $p^n$ is always a quadratic residue $\bmod p^n$ and not $\bmod p^{n+1}$ when $n$ is odd.

  • $\begingroup$ What do you mean by $p \mid a$? $\endgroup$ – Puzzled417 Jan 9 '17 at 4:49
  • $\begingroup$ when $p$ divides $a$ the theorem is not always true. $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:49
  • $\begingroup$ would you agree that $p^3$ is a quadratic residue $\bmod p^3$ but not $\bmod p^4$? $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:51
  • $\begingroup$ I meant to say $0 \leq a < p^n$. $\endgroup$ – Puzzled417 Jan 9 '17 at 4:53
  • $\begingroup$ Oh, in that case It works fine. $\endgroup$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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