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.
Contents |
[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.
[edit] Proof
Any number can be expressed as
We know that under Modulo Arithmetic, 
Thus 
Thus, if the sum of the digits is equivalent to zero (divisible), the number itself is also equivalent to zero (also divisible).
