0
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ Do you mean to ask if it's necessary? $20$ ends in $0$, and $20\equiv0\bmod4$, but $20 $ is not a perfect square $\endgroup$ Jun 21, 2021 at 20:09
  • $\begingroup$ How would I make this sufficient? $\endgroup$
    – dan
    Jun 21, 2021 at 20:13
  • $\begingroup$ $5$ is the smallest counterexample. $\endgroup$
    – paw88789
    Jun 21, 2021 at 20:14
  • $\begingroup$ Then, for numbers greater than 2 digits can we consider this as a test for exclusion from the set of perfect squares? $\endgroup$
    – dan
    Jun 21, 2021 at 20:20
  • $\begingroup$ If it's congruent to $0\bmod n^2$ for any square $n^2$ less than itself, it's not square free ... $\endgroup$ Jun 21, 2021 at 23:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is the math up there going bonkers for anyone else? $\endgroup$ Jun 21, 2021 at 20:21
  • $\begingroup$ So, then, a follow up question is how many residue checks does one have to do for an integer $n$? Is there a hidden inequality in this answer? $\endgroup$
    – dan
    Jun 21, 2021 at 20:37
  • $\begingroup$ let's see. 5 is excluded by residue mod 3 (can only be 0 or 1); so is 20; 21, uh... it's allowed to be 1 mod 2, 0 mod 3, 1 mod 4, 1 mod 5, 3 mod 6, 0 mod 7... but it's not allowed to be 5 mod 8. that's a long way up, and there are easier ways. $\endgroup$ Jun 21, 2021 at 20:56
  • 2
    $\begingroup$ oeis.org/A139401 OEIS to the rescue. that's a pretty small number of entries, if I get bored tomorrow I might send them an extension $\endgroup$ Jun 21, 2021 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .