Check perfect squareness by modulo division against multiple bases I am interested in a quick test to see if a number is a perfect square. One good test is to look at how the number ends. In Base-10, a perfect square ends in 0,1,4,5,6, or 9. This is helpful because I can trivially filter out numbers that end differently before I need to do more expensive operations. 
It's also true that in Base-16, a perfect square ends in 0, 1, 4, or 9. 
However, if we look at the non-perfect-square numbers 11 and 17, we can see 11 passes the Base-10 test, since 11 mod 10 = 1, but fails the Base-16 test (11 mod 16 = 11). Likewise, 17 fails the Base-10 test, but passes the Base-16 test. I think this is because 10 has a factor that 16 doesn't have, but I'm not sure.
It's easy to see that performing both tests will filter out more numbers than either one on its own, and it stands to reason that there exist more bases which filter out additional numbers.
My question is: Why do these two bases test a different set of numbers, and how could I choose a minimal set of bases which filtered out the most numbers?
(I realize any method of choosing bases can be extended infinitely, but infinity and quick don't exactly get along. I'm more curious into the theory behind this, and I can discuss a test coverage vs. speed tradeoff in Stack Overflow).
 A: NOT an answer, but too long to be a comment.
I would like to include a small proof of the statement that you opened with, for some context. If we have some integer in base $10$, it can be represented as
$$n=C_0 10^0+C_1 10^1 +...+ C_k 10^k$$
where each $C_i \lt 10$ and $k+1$ is the number of digits that the integer has. When we square this integer, by expansion, it becomes clear that the only term containing $10^0$ will end up being
$$C_0^2 10^0$$
and, since we want to represent its square in base $10$, the first coefficient of its square must be less than $10$, and so the first digit of its square is
$$C_0^2 \bmod 10$$
and, since $C_0 \lt 10$, the only possible first digits of $n^2$ are
$$1\bmod 10=1$$
$$4\bmod 10=4$$
$$9\bmod 10=9$$
$$16\bmod 10=6$$
$$25\bmod 10=5$$
$$36\bmod 10=6$$
$$49\bmod 10=9$$
$$64\bmod 10=4$$
$$81\bmod 10=1$$
Which proves your statement.
Now we may generalize this to all bases. A number $n$ in base $b$ can be represented by
$$n=C_0b^0+C_1b^1+...+C_kb^k$$
Where each $C_i \lt b$ and $k+1$ is the number of digits of $n$ in base $b$. By following the same path as we did in the last proof, the set of all possible smallest digits is the set
$$\bigcup \limits_{a=1}^{b-1} \{a^2 \bmod b\}$$
let this set contain $l$ elements. Then you are seeking some base $b_m$ for which the ratio of $l$ to $b_m-1$ is minimized.
A: Checking your candidate number $x\bmod 24$ is quite a good option, especially if you first cast out factors of $4$ and $9$ (to get $x'$). Then you need $x'\equiv 1 \bmod 24$ for a candidate square.
The reason lurking behind this is that the Carmichael function $\lambda(24)=2$, so every co-prime squares to $1 \bmod 24$. Dividing out $4$s and $9$s can only leave zero or one factor of $2$ or $3$ respectively in the modified number (one of either would make it non-square). And $24$ is the largest number with $\lambda=2$.
For checking against any other primes, first reduce the candidate by casting out factors of the square of that prime, then half of the possible values will indicate candidate squares - all the even powers of a primitive root.
