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

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

• I thought Hensel's Lemma was elementary.. though this could be because I used them in contests, and not in any study of mathematics. – S.C.B. Mar 21 '16 at 22:53
• @MXYMXY: Actually, it depends on how deep your studies are in number theory. The proof of lemma, especially when we are not dealing with $p$-adic numbers, seems pretty elementary to me, too. But as I'm going to describe it to some undergrad students, I wanted to check out if there's actually a simpler proof. – M.S. Dousti Mar 21 '16 at 22:59

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

• For p=2 (i.e., when p is not odd), the function f(x) can be 4-to-1 (when k>=3). Can we consider this case as well, using your simple counting argument? – M.S. Dousti Mar 21 '16 at 23:36
• One can get a theorem, not the same since if $a$ is an arbitrary odd integer which is a quadratic residue modulo $2$, it is not necessarily a quadratic residue modulo $4$. – André Nicolas Mar 21 '16 at 23:53

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

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

• Thanks a lot. But I think you're actually following Hensel's lemma, without naming it. This is the constructive method which iteratively builds the solutions from the ground up. – M.S. Dousti Mar 21 '16 at 23:22