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

  • $\begingroup$ I thought Hensel's Lemma was elementary.. though this could be because I used them in contests, and not in any study of mathematics. $\endgroup$ – S.C.B. Mar 21 '16 at 22:53
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – M.S. Dousti Mar 21 '16 at 23:36
  • $\begingroup$ 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$. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – M.S. Dousti Mar 21 '16 at 23:22

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.