oblomov, I just realized that all perfect squares mod 9 can only be 0, 1, 4, 7, but I can't find an easier proof than by exhaustion (square all numbers 0 to 8, mod 9). Is there a more elegant proof of this?
mod 11 has a wider choice (0, 1, 3, 4, 5, 9), but I wonder how good of a “perfect square detector” they can be together. Of course if either proof (by 9s and by 11s) fails, it's not a perfect square, but how many “not perfect square” are perfect squares both mod 9 and mod 11?
Add comment