Multiples of 9...

9, 18 (1+8), 27 (2+7), 36 (3+6), 45 (4+5), 54 (5+4), etc.

I was biking the other day and I don't know why but the pattern just hit me. In particular, the ones digit goes down by 1 and the next digit goes up by 1 (that is, unless we cross 0 or 10).

For instance, going from 9 to 18:

• decrement 9 to 8
• increment 0 to 1

Going from 99 to 108:

• decrement the last 9 to 8
• increment the first 9 to 10

We live and breathe in base 10, though, so this should be incredibly underwhelming. But what about counting by 2's in base 3? What does our decimal sequence of even numbers (2,4, 6, 8,...) look like in base 3?

• 2 is just 2
• 4 gets the same decrement/increment algorithm as before: 11
• 6, same deal: 20
• 8? Our algorithm "breaks" until you realise that adding 2 to 20 doesn't need to decrement the ones digit since it's already at zero. We can just add 2! So 8 is 22.
• 10: using our algorithm bumps the first 2 up to 3, which means we've earned a new digit, and our base-3 representation is 101.

Notice the pattern here, too? 2 (2), 4 (1+1), 6 (2+0), 8 (2+2), 10 (1+0+1)... The digits add up to multiples of 2.

There is/was/shouldn't be anything god-given about the number 9. Or the number 2. What connects them is their relationship to the base we chose. 9 is the largest digit value for base 10, and 2 is the largest digit value for base 3. More abstractly: we are looking at $b-1$ for a given base $b$.

I wouldn't be surprised if they taught me this in Algebra 1, but it turns out the pattern we're looking at is far from novel. It's a fairly straightforward consequence of the fact that $b$ always has remainder 1 modulo $b-1$. That is:

$$b \equiv 1 \mod \; b-1$$

or more compactly, if $b^{-} = b-1$, $[b]_{b^-} = 1$.

A pretty straightforward induction shows that

$$b^{i} \equiv 1 \mod b^{-}, \; \forall \; i \in \N$$

Which means that whenever we express a number, $a$, in a given base as

$$a = \sum_{i=0}^{k}d_i b^i \qquad 0 \leq d_i \leq b^-$$

we just apply some simple properties of the modulo operation:

$$[a]_{b^-} = \left[\sum_{i=0}^{k}d_i b^i\right]_{b^-} = \left[\sum_{i=0}^{k}\left[d_i b^i\right]_{b^-} \right]_{b^-} = \left[\sum_{i=0}^{k}\left[d_i \right]_{b^-} \left[b^i\right]_{b^-} \right]_{b^-}$$

and since $[b^i]_{b^-} = 1$ and $0 \leq d_i \leq b^-$ for all $i$:

$$[a]_{b^-} = \left[\sum_{i=0}^{k} d_i \right]_{b^-}$$

Which says that the modulo of the digit-sum of $a$ is the same as the modulo of $a$. Hence, if $a$ is a multiple of $b^-$, then its digit-sum will be a multiple of $b^-$.

Let's try this out with base-10 (hence, $b^- = 9$):

• if $a$ is 51 -- not a multiple of 9 -- 51=5*9+6, so $[51]_9 = 6$. And look at the digit sum! 5+1=6!
• if $a$ is 99=11*9 we get that $[99]_{9} = 0$, and the digit sum is 18=2*9!

I know that, for me, proof by induction can be very unsatisfying and at first glance this all feels like silly number magic. Indeed, it might just be that, but in the process of trying to understand "why 9", I got to practice arithmetic in other bases, and that really solidified the intuition for why the digit sums have to be multiples of $b^-$. Basically, it's all about the decrement by 1 in one position, increment by 1 in the next. That +1, -1 dance keeps the digit-sum in check (so to speak).