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

Question

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.

Answer 1

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.

Answer 2

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