It is known that $N$ is a perfect square if and only if $N$ is a quadratic residue for every prime $p$. This gives a good probabilistic algorithm for testing if a randomly chosen positive integer is a perfect square - simply compute it's Legendre Symbol for a sufficiently large set of randomly chosen primes. A single result of $-1$ definitively tells you that $N$ is not a perfect square, while repeated results of only $+1$ or $0$ increase the probability that $N$ is a perfect square.
This probabilistic test could be much quicker with lower probability of a false positive if we could check only primes less than the integer $N$. The proofs I've seen that $N$ is a perfect square IFF $N$ is a QR mod p for all primes $p$ cannot be used to prove the result using only the finitely many primes less than $N$.
Has anyone seen or know of a proof of this more specific result, or alternatively, know of a counter-example? I've burned more than a few CPU cycles on Mathematica looking for a counterexample and have not found one yet.
No. For example, $\;6\;$ is a quadratic residue mod $\;2,3\;\text{ and }\,5\;$ .