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
• 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$