You're probably aware of the trick to find whether a number is divisible by 9 - if it's divisible by 9, so is the sum of its digits. The same thing works for divisibility by 3. For example:

12345's digits add up to 1+2+3+4+5 = 15 which is divisible by 3, so 12345 is divisible by 3 (it's 4115×3).

10746's digits add up to 1+7+4+6 = 18 which is divisible by both 3 and 9, so 10746 is divisible by both 3 and 9 (it's 3582×3 or 1194×9).

## Proof that this works

It's possible to prove that this will always work - one possible proof is:

Let

mbe ann-digit number, and its digits in reverse order bed_{0},d_{1}, up tod_{n-1}, so eachdis a whole number between 0 and 9 inclusive._{i}This implies that

m=d_{0}+ 10d_{1}+ 100d_{2}+ 1000d_{3}+ ... + 10^{n-1}d_{n-1}⇔m= (d_{0}+d_{1}+d_{2}+d_{3}+ ... +d_{n-1}) + (9d_{1}+ 99d_{2}+ 999d_{3}+ ... + (a number with n-1 digits all of which are 9)d_{n-1})⇔m= (the sum of all m's digits) + 9(d_{1}+ 11d_{2}+ 111d_{3}+ ... + (a number with n digits all of which are 1)d_{n-1})so obviously, if m is divisible by 9, so is the sum of m's digits, and vice versa. Also, since 9 is divisible by 3, the same occurs for 3. QED.

So why 9 and 3? It seems to be because the number 1 less than a power of 10 is a long string of 9s, so it's divisible by 9; and if it's divisible by 9, it must be divisible by 3 too. So the whole trick is a coincidence of the counting system we use.

## Outside base 10

So what would happen if a many-fingered alien who counted in base 37 tried this? Or a computer which counts in base 2? Or a computer programmer who counts in octal (base 8) or hexadecimal (base 16)?

Mathematicians like solving problems by turning them into something they've done already, so let's try adapting the Base 10 method.

Let

mbe ann-digit number in baseb, and its digits in reverse order bed_{0},d_{1}, up tod_{n-1}, so each d is a whole number between 0 andb-1 inclusive.This implies that

m=d_{0}+bd_{1}+b^{2}d_{2}+b^{3}d_{3}+ ... +b^{n-1}d_{n-1}⇔m= (d_{0}+d_{1}+d_{2}+d_{3}+ ... +d) + ((_{n-1}b-1)d_{1}+ (b^{2}-1)d_{2}+ (b^{3}-1)d_{3}+ ... + (b^{n-1}-1)d_{n-1})That doesn't seem so helpful.

In base 10 the powers-minus-1 are helpful, because they are long strings of 9s. However, in arbitrary bases we're not sure what they are.

I write computer programs, so hexadecimal seems a good place to look for patterns. (Note: hex is generally written with a leading "0x" (zero, X) to stop it looking like decimal. Also, the hex digits are 0x1 = 1, ..., 0x9 = 9, 0xA = 10, 0xB = 11, ..., 0xF = 15.)

0x10 - 0x1 = 0xF 0x100 - 0x1 = 0xFF which is 0x11 times 0xF 0x100000000 - 0x1 = 0xFFFFFFFF which is 0x11111111 times 0xF

Looks like we're onto something... does it work in general? Actually, this
works for any base; *b*^{x} - 1 is divisible by (*b* - 1)
for all positive whole numbers *b* and *x*. You can prove this by a method called
induction:

1.b^{1}- 1 =b- 1 so it's obviously divisible by (b-1), for every positive integerb(an integer is just a whole number).

2.Suppose we know thatb- 1 is divisible by (^{k}b-1). Thenb- 1 = (^{k}b-1)afor some integera.Consider

b^{k+1}-1:b^{k+1}-1 =b(b) - 1^{k}⇔b^{k+1}-1 =b(b- 1) +^{k}b- 1⇔b^{k+1}-1 =b((b-1)a) + (b-1) for somea⇔b^{k+1}-1 = (b-1)(ab+ 1)so if

b- 1 is divisible by (^{k}b-1), so isb^{k+1}- 1, for any positive integerb.

3.the quick way: By the principle of mathematical induction,b^{x}- 1 is divisible by (b- 1) for all positive integersbandm.3.the slow way (what the above actually means): The statement is true forx= 1, because we proved this in (1.) Then (2.) means it must be true forx= 2, which means it must be true forx= 3... applying this as many times as you like, it's true for all positive integers.

So, we can get back to where we left off above

m= (d_{0}+d_{1}+d_{2}+d_{3}+ ... +d_{n-1}) + ((b-1)d_{1}+ (b^{2}-1)d_{2}+ (b^{3}-1)d_{3}+ ... + (b^{n-1}-1)d_{n-1})But we've just shown that all the (

b- 1) terms are divisible by (^{x}b-1), so we can call the total (b-1)cfor some integerc. Then we havem= (the sum ofm's digits) + (b-1)cSo if the sum of

m's digits is divisible by (b-1) or any of its factors, so ismitself.

Does this really work? It does; here's a hex example:

0xD7's digits add up to 0xD + 0x7 = 0x14 0x14 is a multiple of 0x5 (since 0x5=5, 0x14=20 in decimal) But 0xF=15, which is one less than 0x10=16, is divisible by 0x5=5 as well So 0xD7 should be divisible by 5... ... and sure enough, 0xD7 = (0xD times 0x10) + 7 = (12 times 16) + 7 = 215 = 43 times 5.

Obviously it'll always work for division by 1, since we're thinking about
positive integers, and they're always divisible by 1. Sure enough, 1 is a factor
of (*b*-1) for all integer bases *b*. A computer counting in binary
only has one non-zero digit to play with, so it's really not particularly
interesting (the trick works for division by 1, but that's obvious). This isn't
particularly useful to a programmer counting in octal either (8-1 is a prime, so
its only factors are 7 and 1), but a programmer working in hexadecimal could use
this for 1, 3, 5 and 15.

So where does this leave our many-fingered, base-37-counting alien? The same sort of trick works in its number system for all the factors of 36. That's 1, 2, 3, 4, 6, 9, 12, 18, and 36...