Divisibility by Seventy-Three

Can you tell whether a large number is divisible by $73$ without actually dividing? You may use the fact that $73 \times 137 = 10001$.

Solution

The key is that $10000$ is one less than $10001$, so $10000$ leaves remainder $-1$ on division by $10001$. Break the number into blocks of four digits, counting from the right, and form the alternating sum of those blocks. The number and that alternating sum leave the same remainder on division by $10001$, and so on division by $73$ as well (and by $137$), since both divide $10001$.

For example, take $84008765$. Its four-digit blocks from the right are $8765$ and $8400$, and $$8765 - 8400 = 365 = 73 \times 5.$$ The alternating sum is a multiple of $73$, so the original number is too, and indeed $84008765 = 73 \times 1150805$. The same blocks show it is not divisible by $137$, since $365$ is not.