# If $a$ is a quadratic residue modulo $p^n$ where $p$ is a prime, then $a$ is a quadratic residue modulo $p^{n+1}$

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.

• what do you mean? is $a$ an integer suuch that its residue class mod $p^n$ is a quadratic residue? – Jorge Fernández Hidalgo Jan 9 '17 at 4:37
• @JorgeFernándezHidalgo Yes, that's right. – Puzzled417 Jan 9 '17 at 4:38
• This is false. 7 is a quadratic residue mod 5 but not 25. – mathworker21 Jan 9 '17 at 4:40
• $7$ is not a quadratic residue $\bmod 5$ – Jorge Fernández Hidalgo Jan 9 '17 at 4:43
• 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 :-) – 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.

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