Proof that this works

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

Let m be an n-digit number, and its digits in reverse order be d₀, d₁, up to d_n-1, so each d_i is a whole number between 0 and 9 inclusive.

This implies that

m = d₀ + 10d₁ + 100d₂ + 1000d₃ + ... + 10^n-1d_n-1

⇔ m = (d₀ + d₁ + d₂ + d₃ + ... + d_n-1) + (9d₁ + 99d₂ + 999d₃ + ... + (a number with n-1 digits all of which are 9) d_n-1)

⇔ m = (the sum of all m's digits) + 9(d₁ + 11d₂ + 111d₃ + ... + (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 m be an n-digit number in base b, and its digits in reverse order be d₀, d₁, up to d_n-1, so each d is a whole number between 0 and b-1 inclusive.

This implies that

m = d₀ + bd₁ + b²d₂ + b³d₃ + ... + b^n-1d_n-1

⇔ m = (d₀ + d₁ + d₂ + d₃ + ... + d_n-1) + ((b-1)d₁ + (b²-1)d₂ + (b³-1)d₃ + ... + (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 = b - 1 so it's obviously divisible by (b-1), for every positive integer b (an integer is just a whole number).

2. Suppose we know that b^k - 1 is divisible by (b-1). Then b^k - 1 = (b-1)a for some integer a.

Consider b^k+1-1:

b^k+1-1 = b(b^k) - 1

⇔ b^k+1-1 = b(b^k - 1) + b - 1

⇔ b^k+1-1 = b((b-1)a) + (b-1) for some a

⇔ b^k+1-1 = (b-1)(ab + 1)

so if b^k - 1 is divisible by (b-1), so is b^k+1 - 1, for any positive integer b.

• 3. the quick way: By the principle of mathematical induction, b^x - 1 is divisible by (b - 1) for all positive integers b and m.
• 3. the slow way (what the above actually means): The statement is true for x = 1, because we proved this in (1.) Then (2.) means it must be true for x = 2, which means it must be true for x = 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₀ + d₁ + d₂ + d₃ + ... + d_n-1) + ((b-1)d₁ + (b²-1)d₂ + (b³-1)d₃ + ... + (b^n-1-1)d_n-1)

But we've just shown that all the (b^x - 1) terms are divisible by (b-1), so we can call the total (b-1)c for some integer c. Then we have

m = (the sum of m's digits) + (b-1)c

So if the sum of m's digits is divisible by (b-1) or any of its factors, so is m itself.

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...