Base conversion divisibility test

The base conversion divisibility test is a process that can be used to determine whether or not a certain (positive) natural number a can be divided evenly into a larger natural number b. It is the general case for the well-known test for divisibility by nine. For other divisors, applying this test is generally harder than figuring it out by normal division.

Example

Is 312 evenly divisible by 13?

• a=13
• b=312
• x=a+1=14
• y=b (base-14)=184 (312 in base x)
• z=1+8+4=13
• z/a=13/13=1, a natural number

312 is evenly divisible by 13.

Dividing by nine

The trick for determining if a number is divisible by nine is well-known: If the sum of the digits of a number is divisible by nine, then the number itself is as well. This is a special case of the general rule, made easy because no base conversion is necessary since 9 + 1 = 10, and we already use base 10.

Example: Is 2,340 evenly divisible by 9?

• a=9
• b=2,340
• x=a+1=10
• y=b (base-10)=2,340
• z=2+3+4+0=9
• z/a=9/9=1, a natural number

2,340 is evenly divisible by 9.

Proof

Any number can be expressed as

$number_{(base)} = \sum_{i=0}^n {digits_i \times base^i}$

We know that under Modulo Arithmetic, $base \equiv_{(base - 1)} 1$

Thus $number \equiv_{(base-1)} \sum_{i=0}^n{digits_i} \times 1$