I recently had a discussion with a good friend of mine, Gordon Bonnar, about the reason why certain tricks for checking the factors of numbers work. The trick we discussed in particular was the commonly used one to know if a number is divisible by three: if the sum of the digits is divisible by three, then the number itself is.
For example, take the number 123. We can quickly see that it's a multiple of three by adding the digits, and seeing if they add up to a multiple of three. 1 + 2 + 3 = 6, so we can see that 123 is divisible by three. This is indeed true, and 123 divided by 3 gives us 41.
The first thought that went through my head on this was that it has to do with the base the number is expressed in. That although it works perfectly in decimal, it may not work in hexidecimal, binary, or various other bases. To test this then, I tried applying this same rule in other numeric bases. The first one I tried was binary, and could immediately see that it does not work. For example, in binary, the number 15 would be expressed as 1111. 1 + 1 + 1 + 1 is not divisible by three, and yet the value itself is.
This is more important than it might at first seem. The fact that it only aplies in certain bases means that the rule is not applicable to the true value of the number. 15 in decimal is exactly the same value as 1111 in binary. There is no difference between those two values; they are identical. The only difference you see is the notation used to express them. This is significant because it means that the rule for checking divisibility by three is not applicable to the value itself, but only to the notation used to express that value.
Much to my surprise though, I found that it does indeed appear to work in other bases. For example, it seemed to work in hexidecimal, and in base 7 when I tried that. It was in seeing which bases work and which ones don't that I realized why this rule works.
When you write a number in decimal, which is how we use numbers on a day-to-day basis, you are expressing it in a numeric base that is one greater than a multiple of three. That is to say, the numeric base we use, 10, is one greater than the value 9, which happens to be a multiple of 3.
Now let's look at multiples of three, not looking as much at the value of the number, but at the digits used to describe that number. Our first three multiples are 3, 6, and 9. What is special about these numbers is the fact that they are each written with their own unique symbol. The first change comes when we hit the next multiple, 12. This is where the value we're expressing becomes greater than the base we're working in. In this case, it does not have a unique symbol. Instead it is expressed by combining two other symbols, 1 and 2.
Consider then why we use the values 1 and 2 to write out the next number. Beyond the fact that this is how the value twelve is expressed, why exactly does it end up being those two digits? There are two reasons why:
First, the value we are incrementing by is less than the base we're expressing it in. That is to say, 3 is less than 10. This is important because it means that each time we increment the value by 3, the "tens" column in the number can only do one of two things: it can increase by one, or it can remain as it is. It can never increase by more than one, because for that to happen, the value we're incrementing by would have to be greater than the base we're working in.
Second, the largest multiple of 3 which is less than 10, is 9. It is important to note this, and realize that 9 is exactly 1 less than the base we're working in, 10.
Look then at what happens to the values of the digits when you add the value 3 to the value 9. The simplest way to look at this is by adding 1, three times in a row. 9 + 1 = 10. So we can see that the "tens" column increases at this point, and the "ones" column is reset to 0. Add another 1, and the "ones" column is increased by one, leaving the "tens" column untouched. Add it again, and the same thing happens, leaving us with the digits "12" and the number twelve.
Notice then that the number used in the "ones" column is now one less than the value 3. This change occurs each time we pass a multiple of ten. So on the first run, the "ones" column contains the values 0, 3, 6, and 9. Then we increment the "tens" column by 1, and the "ones" column goes through the values 2, 5, and 8. Again, the "tens" column is increased by 1, and the "ones" column then goes through the values 1, 4, and 7. Each time the "tens" column is increased by one, the set of numbers used in the "ones" column is decreased by one. As a result of this, the two columns add up to a multiple of three.
This continues until we reach our next digit and go over 100. At that point, we jump from 99 to 102. But because the base we're working in is one greater than a multiple of 3, we see the same effect. Our "tens" column goes from using the digit "9" to the digit "0". Both of those values being multiples of three, this makes no difference in the divisibility of the sum. The "hundreds" column also changes though, going from "0" to "1", so the combined effect of these two columns is to add one to their offset from a multiple of three. In the mean time, the "ones" column continues in the same pattern as before, decreasing the set of digits it uses by one. The net effect then is to maintain that balance in the sum of the digits.
This pattern continues indefinitely and is the reason why our division by three rule works. There are a couple of interesting observations that can be made from this:
- This rule will hold true in other numeric bases that are one greater than a multiple of three. So we know it will work in base 4 arithmetic, base 7, base 13, and so on.
- This rule can be adapted for testing multiples of different numbers in other bases. For example, we can say that in base 11 arithmetic, all multiples of five will have digits that add up to a multiple of five. I can say that the base 11 number "1A73695194" is divisible by five, without even understanding the value of the number*.
*For the cynics out there, that number, 1A73695194 (base 11) is equal to 4644366335 in decimal, which is indeed divisible by 5.