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).