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

  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Mar 20 '15 at 6:07
  • $\begingroup$ Ah yes, that reminds me $\endgroup$ – frogeyedpeas Mar 20 '15 at 10:14

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.

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

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.