Base conversion divisibility test

From Wikipedia, the free encyclopedia

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.

1 The Method
2 Example
3 Dividing by nine
4 Proof

[edit] The Method

Add 1 to a. Call this x.
Convert b to base x. Call this y. (See the note below for handling bases greater than 10.)
Add (in base-10) each separate digit in y. Call this z.
If z / a (in base-10) equals any natural number, then b / a equals a natural number, and b is therefore divisible by a.

Note: When x is 11 or greater, it's easiest to not use hexadecimal-style letters in the converted number. Rather, use the two (or more) digits together as one digit. So that you know that they are one digit, put them in parentheses or brackets. For example, convert 638 to base-20 as 1(11)(18). The "digits" then sum as 1 + 11 + 18 = 30.

[edit] 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.

[edit] 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.