Geek Blight

Let’s use base 10 and number 3 as an example. In the way we represent numbers, we have 10 digits (0 to 9). A number is represented by a sequence of digits whose value is bigger the more to the left it is. In number 234, the digit 2 represents the value 200, the digit 3 represents the value 30 and the digit 4 represents the value 4. When counting from zero, we start by increasing the rightmost digit until it reaches the value 10. When that happens, the digit rolls over back to 0 and we increase the digit to its left. So if we try to write the multiples of 3, we have a coincidence that makes the method work. We start by 03, then 06, then 09 and…​ whoops, the next will be twelve, but the rightmost digit rolls over to 0 when increased once, and to 2 when we increase it twice more as needed. The digit to its left is increased. So we jump from 09 to 12. This increase of the digit to the left compensates the value we lost in the rightmost digit as when multiplying the highest possible multiple of 3 before 10 is precisely 9, one less. So in the first round we passed by 3, 6 and 9. In the second round, thanks to 10 % 3 = 1, we are going to pass by those minus 1: 2, 5, 8. Yet the sum of the digits is still 3 because the digit 1 appears to their left forming the numbers 12, 15 and 18. In the next round we pass through digits 1, 4 and 7. The sum is still 3 because the leftmost digit will be increased to 2 to give numbers 21, 24 and 27. In the next number we go back to the original digits (plus 0) but the leftmost digit is increased again for the third time, resulting in a multiple of 3: 30, 33, 36, 39. Well, this is pretty easy to understand.

Now, what happens with the rest of the digits? The rightmost digit is always increased this way, but the rest of the digits are increased normally one by one until they roll over again. For example, what happens at 99? Sure, the rightmost 9 changes to 2 and, to compensate, we would have to increase the leftmost 9 to "ten", but we can’t do that. The 9 on the left will become 0 and a new 1 will appear on the left, to form number 102. How is the condition still true? Let’s see. If the rightmost 9 rolls to 2, the leftmost 9 should become "ten" for the condition to be met. Instead, its value becomes 0. That’s 10 less than what we expected. Yet the rightmost digit is increased by 1, so we’ve got 10 less than expected on the middle digit, but one more on the leftmost digit. Summing up, we have a sum that falls short by 9 (in general, base - 1), which is a multiple of 3! From (9,9), total sum 18, we wanted to go to (10, 2), which is impossible, so we went to (1, 0, 2). (10, 2) would sum 12. (1, 0, 2) sums 3, that is, 9 less as we just explained. Sometimes this event triggers more than once. Let’s take 9999. The last 9 rolls over to 2. It would be fine if the 9 to its left becomes 0 and we increase the digit to the left of that 9. Which we can do…​ oops! No, we can’t make that, but we can make it 0 and make the leftmost digit a…​ oops! No, it will have to become 0 and we’ll add a 1 to the left. Result: 10002. The property is kept.

The only question remaining in your head could be (maybe not): when the value of the sum is decreased as we just see, isn’t it possible to be left with a number that is not a multiple of 3? But the answer is no. If the sum is a multiple of 3 and we substract 9, the resulting sum is either 0 (which is impossible because every number greater than 0 has at least a nonzero digit) or another multiple of 3, by definition. So it always works.

Dr. Math explains this very easily. He says: let’s have a number formed by two digits: ab. The value of that number is, in decimal, 10*a + b. Now, 10*a + b = (9*a + a) + b = 9*a + (a + b). 9*a is a multiple of 3 because it’s a multiple of 9. So 10*a + b (our number) is a multiple of 3 if (a + b) (the sum of its digits) is also a multiple of 3. The same can be exposed for a number composed of 3, 4…​ N digits. For example, for 3 digits abc, the number can be expressed as 99*a + 9*b + (a + b + c).

Let’s generalize that for any base and any digit for which (base % digit) = 1. Let’s call the base B and the digit D. This number has digits numbered from 0 (rightmost) to N (leftmost). These digits are called X0…​ XN. This number can be expressed as SUM { B^i * Xi for i in [0, N] }. As Dr. Math showed, we can also decompose this sum as SUM { (B^i - 1) * Xi for i in [1, N] } + SUM { Xi for i in [0, N] }. The second part is the sum of its digits. If we can prove that the first part is a multiple of D, we can conclude that the sum of the digits must be then a multiple of D too. To prove that the first part is a multiple of D, we’ll try to prove that (B^i - 1) is a multiple of D. If that’s true, as it seems to be (9, 99, 999 were multiples of 3), then (B^i - 1) * Xi is a multiple too, and the sum of them is a multiple too. So the key here is to prove that (B^i - 1) is a multiple of D for any i. If (B^i - 1) is a multiple of D ((B^i - 1) % D = 0), then, by definition of how the division operation works, B^i % D = 1. We need to prove that B^i % D = 1 knowing that B % D = 1.

Let’s stop here for a moment and remember the rules of modular arithmetic for sums. (a + b) % c = a % c) + (b % c % c. This is more or less trivial. Let’s suppose you have to divide the contents of two bags, one with a items and the other one with b items. This rule tells us that to know the remainder of that division we can put all the items together and divide, or we could also divide the contents of each bag individually, put together the remainders and divide again. This works for any number of "bags". Let’s translate this to multiplication. (a * b) % c = (a + …​ (b times) …​ + a) % c = a % c) + …​ (b times) …​ + (a % c % c = a % c) * b) % c. And finally translate this rule to powers, what we need: B^i % D = (B * B^(i - 1 % D = B % D) * B^(i - 1 % D. But we know that (B % D) == 1, so this is equal to B^(i - 1) % D. So we have that B^i % D = B^(i - 1) % D = …​ = B % D = 1. QED.

With our notation system, under any base, if the remainder of the division of the base by a digit is 1, the sum of the digits in any multiple of that original digit is also a multiple of the original digit.

Note that in the last step of the demonstration we could have concluded that B^0 % D = 1 % D = 1. This is not a problem, because the only digit that wouldn’t allow this is 1, but in that case B % D couldn’t be 1 either (one of our conditions). It would be 0.