Can an integer pretend to be a square and yet not be a square? So let n be an integer which is not a square – can it be a quadratic residue modulo every prime? No. Indeed, suppose n is squarefree (square factors don’t alter the property of being a square or quadratic residue) and write n=p_1\cdots p_k. Suppose none of the p_i is 2 first. We want to find a prime q such that (\frac{n}{q})=\prod (\frac{p_i}{q})=-1. If k=1 (n is prime), it’s easy because of the quadratic reciprocity law: if n=1 [4], (\frac{n}{q})=(\frac{q}{n}) so we just have to find q which is not a square modulo n, which is the case of about the half of the residues so it shouldn’t be too hard. In general, we can even find q=1[4] with (\frac{p_1}{q})=-1 and the Legendre symbol equal to +1 for the other primes: indeed, (\frac{p_i}{q})=(\frac{q}{p_i}) then and it will be +1 if q=1[p_i]. By Chinese remainder theorem, imposing a condition modulo each p_i (q=1[p_i] for i>1 here, and q=a_{p_1}[p_1] for a fixed non-quadratic residue a_{p_1}) and modulo 4 amount to imposing a condition q=b[4n] with b\leq 4n.
And by Dirichlet’s theorem, there exists a prime number in this progression. If n is even (p_1=2, say), we argue similarly except that we must replace the quadratic reciprocity law by
the formula (\frac{2}{q})=(-1)^{\frac{q^2-1}{8}}. Thus we can for instance decide that q=5[8], thus for the odd factors (\frac{p_i}{q})=(\frac{q}{p_i}) and we can ensure these symbols are all 1 by taking a number belonging to suitable classes.

It is not too easy to bound such a q. In the case where n is prime, there is the terribly difficult Vinogradov’s conjecture which states that there should exist a q\leq\sqrt{n} non quadratic residue modulo n. But then you have to find a prime number in the congruence classe q \text{ mod } n. Linnik’s theorem ensures the existence of a prime number \ll n^L for some constant L (5.5 would do but it’s quite big, 2 is conjectured to work as well).

However, it’s a classical question in sieve theory (see an exercise in Tenenbaum’s book, chapter 4 or in Luca-de Koninck chapter 12) to ask how many n\leq x there are such that n is a quadratic residue modulo every prime p\leq\sqrt{x}. The answer is: between \lfloor\sqrt{x}\rfloor (the number of squares) and C\sqrt{x} for some constant C. The necessary restriction to p\leq\sqrt{x} is a feature of the large sieve. So there are certainly numbers who « pretend to be squares » but which are not.