Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k

Question

In article solving quadratic congruences, it is shown how to use Hensel's lemma to iteratively construct solutions to to $x^2 \equiv a \pmod{p^k}$ from the solutions to $x^2 \equiv a \pmod{p}$. The case where $p=2$ is treated separately.

While the construction is elegant, it is a tad lengthy and its reliance on Hensel's lemma makes it a bit far from elementary number theory.

If we are only concerned with an existential proof (rather than a constructive one), can we simplify the proof? That is, is it possible to succinctly prove the following theorem without resort to Hensel's lemma?

For any prime $p$ and any $k \in \mathbb{N}$, if $x$ is a quadratic residue mod $p$, then it is a quadratic residue mod $p^k$.

Answer 1

We give a counting argument. Let $p$ be an odd prime, and suppose that $a$ is not divisible by $p$. Then the congruence $x^2\equiv a\pmod{p^k}$ has either no solution or two solutions.

To prove this, suppose $b^2\equiv a\pmod{p}$. Then from $x^2\equiv b^2\pmod{p^k}$ we conclude that $p^k$ divides $(x-b)(x+b)$. Since $p$ cannot divide both, we conclude that $p^k$ divides one of $x-b$ or $x+b$. So if the congruence has at least one solution $b$, it has exactly two, namely $b$ and $-b$.

The function $f(x)=x^2$ (modulo $p^k$) maps the set $H$ of numbers between $1$ and $p^k-1$ that are not divisible by $p$ to $H$. By the above, this function is two to one.

So half of the elements of $H$ are QR of $p^k$, and half are not. Which half? The ones congruent to a quadratic residue modulo $p$. For if $a$ is not a square modulo $p$, it cannot be a square modulo $p^k$.

The above argument proves that for odd primes $p$, every quadratic residue modulo $p$ is a quadratic residue modulo $p^k$. The result does not hold for $p=2$: Note that $3$ is a quadratic residue of $2$ but not of $4$.

Answer 2

I have long appreciated this result in LeVeque's Fundamentals of Number Theory, Theorem 4.4:

Suppose $p$ is a prime relatively prime to $a$. Let $t_n$ be the order of $a$ modulo $p^n$ and assume that $p^z$ exactly divides $a^{t_1} - 1$. Then if $p > 2$ or $z > 1$,

$$ t_n = \begin{cases} t_1, \quad &\text{for $n \leq z$}\\\\ t_1 p^{n-z}, \quad &\text{for $n > z$.}\end{cases}$$

This result can be used to prove several congruences mod a prime power that are otherwise messy and annoying to prove (for instance, see Other ways to deduce Cyclicity of the Units of certain groups?).

In your question, if $a$ is a quadratic residue modulo $p$, then $t_1$ divides $\frac{p-1}{2}$. Thus in both of the above cases, $t_n$ is a divisor of $p^{n-1} \cdot\frac{p-1}{2} = \phi(p^n)/2$, so $a$ is a quadratic residue modulo $p^n$.

Answer 3

Suppose $x^2 \equiv a \mod p$, where $a \not\equiv 0 \mod p$, and $p$ is an odd prime. Then $x^2 \equiv a + m p \mod p^2$ for some $m$. Now if $y = x + z p$, $y^2 \equiv x^2 + 2 x z p \equiv a + (m + 2 x z) p \mod p^2$. Thus what we need is $m + 2 x z \equiv 0 \mod p$. But $2x$ is invertible mod $p$, so just take $z \equiv m (2 x)^{-1} \mod p$.