Base conversion divisibility test

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (November 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.


[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

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

Thus, if the sum of the digits is equivalent to zero (divisible), the number itself is also equivalent to zero (also divisible).