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 Jun 12 '18 at 8:11
  • $\begingroup$ @quantum Indeed, but what elementary proof is there of that? $\endgroup$ – Rosie F Jun 12 '18 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$ – Gerry Myerson Jun 12 '18 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 Jun 12 '18 at 9:26
  • 2
    $\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 Jun 14 '18 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.