Generalized Divisibility Rules

On my divisibility page, you may have noticed the rule for divisibility by 7, which is somewhat complicated. It turns out that is is possible to find such divisibility rules for any numbers, even if they don't have a simple rule.

If we want to check a number (call it p) for divisibility by another number (call that number n), we would like to have a weighted sum of p's digits such that p is a multiple of n if and only if that sum is a multiple of n. We can always come up with such a sum for any n, namely 1 × the one's digit + 10 × the ten's digit + 100 × the hundreds digit + 1000 × the thousands digit + ... . However, that sum doesn't help us much because, while it always works, it also always results in the original number so we haven't saved ourselves any time.

The key to making progress here is to realize that if 1 × the one's digit + 10 × the ten's digit + 100 × the hundreds digit + ... results in a multiple of n whenever the original number itself is divisible by n, then 1 × the one's digit + any number congruent to 10 (mod n) + any number congruent to 100 (mod n) + ... will have the same property, because adding or subtracting multiples of n won't affect that property. Therefore, we can simplify that formula by finding numbers congruent to 10, 100, 1000, etc. (mod n) with the smallest absolute value.

Here is a table of some values for certain values:

Note that once you get a repeat weight, the pattern starts to repeat. For 7, for example, the weight of the 10,000,000s' digit is 3, the weight of the 100,000,000s' digit is 2, and so on. Note that the pattern for 19 goes on for a few more places than shown before repeating.

This helps to explain why the divisibility test for numbers that are powers of 2 and/or 5 involves looking at the last few digits. After a while, all powers of ten are congruent to 0 (mod that number) and so can be ignored by our divisibility test. With this, we are able to find patterns for all numbers. For very large numbers, using such a divisibility test is often easier than actually dividing a number in order to determine whether a number divides that large number.

This can get a little cumbersome for some prime numbers, so you may want to look into some alternate divisibility tests.