# Do there exist Artificial Squares?

Denote an artificial square E as a number:

$$E \in \Bbb{N}| \lnot (\exists y \in \Bbb{Z} | y^2 = E) \land (For \ each \ w \in \Bbb{Z} \ \exists a_w | a_w^2 \equiv E \ \pmod w)$$

In other words this numbers are able to pass every square test via modular arithmetic, but aren't squares themselves.

My guess is they don't exist. Simply because for a sufficiently large w. It will be clear that no number squares to E but I'm not sure if this is rigorous enough of an argument, or if I have somehow forgotten detail

• No, you need an actual argument. How do you know that for large $w$ no number squares to $E$? Don't forget that a number larger than $E$ could also square to $E$ modulo $w$. – Yuval Filmus Mar 20 '15 at 6:07
• Ah yes, that reminds me – frogeyedpeas Mar 20 '15 at 10:14

## 1 Answer

Suppose that $E = p^{2k+1} n$ where $(n,p) = 1$. Take $w = p^{2k+2}$. If $E$ is a quadratic residue modulo $p^{2k+2}$ then there exists $m$ such that $$p^{2k+2} \mid p^{2k+1} n - m^2.$$ In particular, $p^{2k+1} \mid p^{2k+1} n - m^2$ and so $p^{2k+1} \mid m^2$. Since $m$ is a (bone fide) square, in fact $p^{2k+2} \mid m^2$, and so $p^{2k+2} \mid p^{2k+1} n$. But that implies $p \mid n$, contradicting our initial assumption.

• This was very clean. What was your motivation behind this particular strategy :) – frogeyedpeas Mar 20 '15 at 10:16
• @frogeyedpeas That was just the first idea that came to mind. – Yuval Filmus Mar 20 '15 at 11:01