# A square modulo every prime is a square. Proof valid?

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, $$(kp^{r-1}+x)^2=jp^{r-1}+a\mod p^r$$ for some $$0\leqslant j.

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 are the values $$jp^{r-1}+a$$ for $$0\leqslant j 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.

• Isn't this just a local-global principal? – quantum Jun 12 '18 at 8:11
• @quantum Indeed, but what elementary proof is there of that? – Rosie F Jun 12 '18 at 8:15
• 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? – Gerry Myerson Jun 12 '18 at 8:53
• 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. – Ingix Jun 12 '18 at 9:26
• @DavidDiaz You have to take care to choose $p$. 7 is a square modulo each of 19, 29, 31, 37, 47, 53, 59. – Rosie F Jun 14 '18 at 7:03