Squares in $\mathbb{Z}_p$ that are not squares in $\mathbb{Z}$ The following question popped up during a conversation with a friend of mine: is there any integer $n$ such that $n$ is not a square in $\mathbb{Z}$ but it is a square in every field $\mathbb{Z}_p$ with $p>n$?
It sounds like an elementary question, and I am almost sure that the answer is no (mostly because of some distant memories of mine about a theorem of Hasse and Minkowsky), but I was not able to find a definitive answer.  
I tried to apply some Model Theory to it, but I don't think it can be a fruitful path to follow. Another thing I noticed is that if I can prove that there is an $a$ such that $n=a^2$ in two different fields $\mathbb{Z}_p$ and $\mathbb{Z}_q$, then the the statement must be false: otherwise, writing $$a^2=n+bp$$ and $$a^2=n+cq$$ for the smallest possible $b$ and $c$, we would have $bp=cq$, a contradiction since neither $b$ nor $c$ can be $0$. But again, I got stuck after this consideration. Do you have any ideas or suggestions?
 A: This is the famous fake square problem (or, at least, I love to call it this way).
Assume that $n\in\mathbb{N}^+$ is not a square but it turns to be a quadratic residue $\!\!\pmod{p}$ for any prime $p$. Let $q_1,\ldots,q_k$ be the primes appearing in the factorization of $n$ with an odd exponent ($k\geq 1$ since $n$ is not an integer square) and let $\eta_k$ be the least quadratic non-residue $\!\!\pmod{q_k}$. By Dirichlet's theorem there is a prime $r$ such that 
$$r\equiv 1\!\!\!\!\pmod{4},\;r\equiv 1\!\!\!\!\pmod{q_1},\;\ldots\;, r\equiv 1\!\!\!\!\pmod{q_{k-1}},\; r\equiv \eta_k\!\!\!\!\pmod{q_k}.$$
For such prime $r$, by the multiplicativity of the Legendre symbol and quadratic reciprocity we have:
$$\left(\frac{n}{r}\right)=\prod_{h=1}^{k}\left(\frac{q_h}{r}\right)=\prod_{h=1}^{k}\left(\frac{r}{q_h}\right)=-1$$
hence $n$ is not a quadratic residue $\!\!\pmod{r}$, contradiction.

One might wonder if there are integers that differ from any sum of two non-negative integer cubes, but can be represented as $x^3+y^3\pmod{p}$ for any prime $p\equiv 1\pmod{3}$. Since the non-trivial integer solutions of $a^3+b^3=c^3+d^3$ are known as the taxicab numbers, we may call the problem presented after the breakpoint as the fake taxi problem. (;P)
