As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?"

Theorem. Any integer which is a square modulo every prime is a square.

Lemma. For any odd prime $p$, any integer which is a square modulo $p$ is a square modulo every power of $p$.

Proof. Let $a$ be any square modulo $p$. Let $r$ be any integer $\geqslant 1$. Use induction on $r$. (I adopt this approach to avoid a bug, spotted by Ingix, in my earlier proof.) The result is true for $r=1$. Suppose, by the inductive hypothesis, that $a$ is a square modulo $p^{r-1}$. Then $a=x^2\mod p^{r-1}$ for some $x$.

Work modulo $p^r$. If $x=0$ then $a=0=0^2$ modulo $p^r$. Otherwise, for $0\leqslant k<p$, $(kp^{r-1}+x)^2=jp^{r-1}+a\mod p^r$ for some $0\leqslant j<p$.

Suppose two distinct $kp^{r-1}+x$ had the same square. Then \begin{align*} (kp^{r-1}+x)^2&=(lp^{r-1}+x)^2\mod p^r\tag{ with $k\ne l$}\\ (k^2-l^2)p^{2r-2}+2(k-l)p^{r-1}x&=0\mod p^r\\ 2(k-l)p^{r-1}x&=0\mod p^r\tag{ as $r>1$}\\ 2(k-l)x&=0\mod p \end{align*} $p$ is an odd prime and $x\ne 0\mod p$, so $p\nmid 2x$, so the last line is false.

Therefore, by the pigeonhole principle, the values of the $p$ distinct expressions $(kp^{r-1}+x)^2$ for $0\leqslant k<p$ are the values $jp^{r-1}+a$ for $0\leqslant j<p$ in some order. In particular, in one case $j=0$, so $a$ is a square modulo $p^r$.

Proof of theorem. Let $a$ be a square modulo every prime. Then, by Lemma 1, $a$ is a square modulo every odd prime-power. Then, by the Chinese remainder theorem, $a$ is a square modulo every odd integer. Then, by Eric Schneider's argument, with $n=2$, but applying it only to $p$ being an odd prime and not to $p=2$, for every odd prime $p$, $p^r\; ||\;a$ for an even number $r$.

Thus either $a=x^2$ or $a=2x^2$ for some integer $x$. Let $p$ be a prime where $p=\pm 3\mod 8$. Then, modulo $p$, $a$ is a quadratic residue modulo $p$ by supposition, but 2 is not a quadratic residue, so $2a$ is not a quadratic residue, so $2a$ is not a square in $\mathbb{Z}$. Thus for every integer $x$, $(2x)^2=4x^2\ne 2a$, so $2x^2\ne a$, so $a$ is a square, as required.

I see no elementary proof of this theorem, with no use of quadratic reciprocity (QR). I wonder if the above qualifies. Chan asked for a proof of this very result but that question was closed as a duplicate of a different question, viz the one where Eric Schneider's answer has been used above. There is Hagen von Eitzen's proof of a similar result, but that relies on QR. ArithmeticGeometer requested a proof without using QR, and the only answer is an advanced proof.

  • $\begingroup$ Isn't this just a local-global principal? $\endgroup$
    – quantum
    Commented Jun 12, 2018 at 8:11
  • $\begingroup$ @quantum Indeed, but what elementary proof is there of that? $\endgroup$
    – Rosie F
    Commented Jun 12, 2018 at 8:15
  • $\begingroup$ Quadratic Reciprocity is generally considered to be elementary. It's in most elementary Number Theory textbooks, it requires no complex variables – what's not elementary about it? $\endgroup$ Commented Jun 12, 2018 at 8:53
  • 1
    $\begingroup$ For different people elementary means different things, I certainly don't find the usual proofs of quadratic reciprocity elementary. For the OP, the first error I found (didn't look any further) is that you concluded from $k \ne l$ that you could divide an equation by $(k-l)$ and still go from mod $p^{r-1}$ to mod $p^{r-1}$. If $k-l$ is a multiple of $p$, this is not valid. $\endgroup$
    – Ingix
    Commented Jun 12, 2018 at 9:26
  • 3
    $\begingroup$ @DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59. $\endgroup$
    – Rosie F
    Commented Jun 14, 2018 at 7:03

1 Answer 1


That $a$ is a square $\bmod p$ implies that $a$ is a square modulo every $p^k$ whenever $p$ is an odd prime not dividing a. If $p^{2m+1}\| a$ then it fails for $k>2m+1$.

  • $\begingroup$ Oh dear. It is for those primes dividing $a$ that my proof of the theorem needs my lemma. So my proof seems to be irreparable. Indeed the whole point of the lemma (lifting from mod $p^{r-1}$ to mod $p^r$) isn't really needed --- you could try proving the theorem by contradiction, letting $a$ be its lowest counterexample. It is then easy to see that $a$ is square-free, i.e. the product of distinct primes. Multiplicities don't come into it --- the issue is, what could the primes be. $\endgroup$
    – Rosie F
    Commented Dec 7, 2020 at 10:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .