arithmetic – Lucky's Notes

The divisibility test for 3 and 9 is fairly well known. To find out of any given integer is divisible by 9, add up the digits of the number; if the result is divisible by 9 then the number is divisible by 9.

What’s a bit less well known is that in any base b, the same trick applies for b-1 and all of its divisors.

For example, if we are doing arithmetic in hexadecimal (base 16), the divisibility rule we use for base 10 applies not for 3 and 9, but instead for 3, 5, and 15.

Suppose we were to confirm that $\textrm{831f3f}_{16}$ is divisible by $\textrm{f}_{16}$ . Adding up the digits:

$\begin{array}{l} 8_{16} + 3_{16} + 1_{16} + \textrm{f}_{16} + 3_{16} + \textrm{f}_{16} \\ = \textrm{2d}_{16} \end{array}$

And since $\textrm{2d}_{16}$ is divisible by $\textrm{f}_{16}$ , so is the original number.

Proof

Let n be an integer, b be the base, and m be the number of digits in n. Then we can represent n:

$n = d_{m-1} b^{m-1} + d_{m-2} b^{m-2} + \cdots + d_1 b + d_0$

We can rearrange this:

$\begin{array}{rl} n =& [d_{m-1} (b^{m-1}-1) + \cdots + d_1 (b-1)] \\ &+ (d_{m-1} + d_{m-2} + \cdots + d_1 + d_0) \end{array}$

Each of the expressions $b-1$ , $b^2-1$ , up to $b^{m-1}-1$ are divisible by $b-1$ . I’ve explored the proof for this in an earlier blog post.

Thus the entire first group of the above expression is divisible by b-1. What remains is the second group, which happens to be the sum of digits in n.

The sum of digits in n is divisible by b-1 if and only if n is divisible by b-1, which is what we wanted to prove.

For a factor of b-1, this also works as the entire first expression is divisible by any factor of b-1.

Lucky's Notes

Notes on math, coding, and other stuff

Tag: arithmetic

Digit sum divisibility rule proofs in bases other than 10

Proof