Testing membership for perfect square number

125 Views Asked by At

Is it sufficient to test that if a positive integer $n$ ends in $0, 1, 4, 5, 6, 9$, and that $n \equiv 0, 1 \bmod 4$ then $n$ is a perfect square?

The numbers $0, 1, 4, 5, 6, 9$ I got from the quadratic residues mod 10. These proved that all perfect squares have these numbers as their final digit in decimal notation.

Are there better methods to test whether a number $n$ is a perfect square?

For example, the number $3190491$ ends in $1$, and $3190491 \equiv 3 \bmod 4$, therefore it is not a perfect square. But the number $100 \equiv 0 \bmod 4$ and ends in $0$.

1

There are 1 best solutions below

4
On

The tests you have give: $0, 1, 4, 5, 9, 16, 20, 21, 24, 25, 29, 36, 40, ... 20n, 20n+1, 20n+4, 20n+5, 20n+9, 20n+16$. This obviously is too many: squares get rarer as you go up, these things don't. In fact, there is no finite combination of residue checks that you can perform to affirm that a number is a perfect square, for this same reason: no matter how many residue checks you do, you can replace them with a single very large residue check, and the things that pass that residue check do not get rarer as the numbers get larger.