A fun exercise is to think about the divisibility tricks you learned in grade school and generalize them to different bases. In base 10 we have:
N is divisible by 2 if its last digit is divisible by 2
N is divisible by 3 if the sum of its digits is divisible by 3
N is divisible by 4 if its last two digits are divisible by 4
N is divisible by 5 if its last digit is 0 or 5
N is divisible by 6 if N is divisible by 2 and 3
N is divisible by 7 if N = Xy for a single digit y and X – 2y is divisible by 7
N is divisible by 8 if its last three digits are divisible by 8
N is divisible by 9 if the sum of its digits is divisible by 9
N is divisible by 10 if its last digit is 0
N is divisible by 11 if the alternating sum of its digits is divisible by 11
There are a few natural categories of divisibility rules here. Divisibility by 3 and 9 are both tested by taking a sum of the digits of N. Divisibility by 11 is checked with an alternating sum. Divisibility by 2, 4, 5, and 8 is tested by looking at the last few digits of N. Divisibility by 6 is a combination of two other divisibility rules. And divisibility by 7 is in its own category.
Sum Test
To test divisibility of N by k, check if the sum of digits of N is divisible by k.
In base B, this test can be used whenever k divides B – 1. For example, in base B = 10, we use the sum test only to test divisibility by numbers that divide 9, i.e. 3 and 9.
Alternating Sum Test
To test divisibility of N by k, check if the alternating sum of digits of N is divisible by k.
In base B, this test can be used only if k divides B+1. For example, in base B = 10, we use the alternating sum test only to test divisibility by numbers that divide 11, i.e. 11.
Ending Test
To test divisibility of N by k, check if the last m digits of N is divisible by k.
In base B, this test can only be used if k divides B, or is a power of some number that divides B. For example, in base B = 10, we use the ending test only to test divisibility by numbers that divide 10, i.e. 2, 5, and 10, and powers of those numbers, i.e. 4, 8, 16, and 25.
Combination Tests
In any base B, to test divisibility of N by k = ij, where i and j are co-prime, it suffices to check divisibility by i and divisibility by j.
So for instance, divisibility by 6 can be checked by performing the tests for 2 and 3, but divisibility by 12 can’t be checked by performing the tests for 2 and 6.
Other Tests
The test for divisibility by 7 in base 10 doesn’t fit into any of the previous categories.
We’ll only be considering the first four categories.
—
There’s a nice way to see why these tests generalize in the way that they do. Let’s think about the sum test first.
Sum Test
We reason it through by induction. Suppose that we’re in base B, and checking divisibility by K < B. Our base case is that the sum of the digits of K is just K, which is divisible by K. For our inductive case, assume that every number n less than N, n is divisible by K if the digits of n add up to something divisible by K. Now, N = (N-K) + K, and (N-K) < N, so (N-K) satisfies the inductive hypothesis. This means that we just need to show that if we start with a number whose digits add to a multiple of K, and add K to this number, the sum of the digits of the resulting number will also be a multiple of K.
Break this into a few cases: First, adding K only affects the last digit. Then the last digit increases by K, so the sum of digits increases by K, and is thus still divisible by K.
What if adding K makes the last digit larger than B? Then we subtract B from the last digit, and add 1 to the second-to-last digit. So the net change in the digit sum is +1 + (K – B) = K – (B – 1)
But adding 1 to the second-to-last digit might also have resulted in a digit larger than B. In this case, we decrease the second-to-last digit is by B and add 1 to the the third-to-last digit. The net change here is -(B – 1).
If this causes the third-to-last digit to exceed B, then the same thing happens, and the net change in the sum of digits from those two is another -(B – 1)
In sum, this tells us that by adding K, the change in the digit sum is one of the following:
+K
+K – (B – 1)
+K – 2(B – 1)
+K – 3(B – 1)
…
In general, the change in the digit sum is +K – n(B – 1) for some n. If we now assume that (B-1) is a multiple of K, then the change in the digit-sum is also a multiple of K. And thus the resulting digit sum will be a multiple of K as well!
So for any K such that B – 1 is a multiple of K, if the digit sum of N is a multiple of K, then N is a multiple of K!
Alternating Sum Test
We can reason it through similarly for the alternating sum test. The possible changes to digits are:
+K
+1, +K – B
+1, +1 – B, +K – B
+1, +1 – B, +1 – B, +K – B
+1, +1 – B, +1 – B, +1 – B, +K – B
…
The alternating sum of this pattern, starting from the far right, gives:
K
(K – B) – 1
(K – B) – (1 – B) + 1
(K – B) – (1 – B) + (1 – B) – 1
(K – B) – (1 – B) + (1 – B) – (1 – B) + 1
…
The result of this sum is always either K or K – (B + 1). So as long as B+1 is a multiple of K, then the alternating sum will also change by a multiple of K!
Thus for any K such that B+1 is a multiple of K, if the alternating sum of the digits of N is a multiple of K, then N is a multiple of K.
—
If we disregard the “Other Tests” category, we can quite easily count for any given base how many digits will have sum, alternating sum, ending, or combination tests. People sometimes say that highly composite numbers would be ideal choices for numerical base systems, but those are really only good for ending tests, and not necessarily for sum or alternating sum tests.
I’ll define the notion of the orderliness of N as the amount of numbers 2 ≤ n < N that have a divisibility rule in base N, restricting divisibility rules to sum tests, alternating sum tests, ending tests, and combination tests.
Here’s a plot of the orderliness of bases from 3 to 100:
And from 3 to 1000:
The jaggedness of this graph suggests that some numbers make much better bases than their neighbors. By analogy to the notion of highly composite numbers, I’ll define highly ordered numbers as those whose orderliness is larger than all smaller numbers. These are numbers that would be ideal choices for numerical bases. The first few highly ordered numbers are:
3, 4, 5, 6, 8, 9, 10, 11, 14, 19, 20, 21, 29, 34, 49, 50, 55, 56, 69, 76, 90, 91, 99
Notice that 12 isn’t on this list, despite being highly composite! You might be able to guess why: though 12 has lots of factors, its neighbors 11 and 13 do not. On the other hand, 11 doesn’t have a lot of factors, but its neighbors 10 and 12 do, so it lands a spot on the list.
We could also measure orderability by what percentage of smaller numbers have rules for them. Here’s what that looks like:
