Friday, November 20, 2009

General rules of divisibility for all bases

I has discovered some interesting traits when I was studying prime numbers. It's a common rule that if the sum of digits of a decimal is divisible by 9, then the decimal is divisible by 9. I tried this rule for a number in base 3, and divided it by 2, interestingly enough, the sum of digits of this based-3 number appears to be divisible by 2. Thus I googled and found this useful stuff:-

Given a number in base B,
  1. If the sum of digits is divisible by B-1 (or one of the factors of B-1), the number itself is divisible by B-1 (or that factor). For B = 10, this holds for 9 and 3.

    E.g. 145283769 / 9 = 16142641 >> 1+4+5+2+8+3+7+6+9 = 45 (4 + 5 = 9 too)

  2. If the alternating sum of digits is divisible by B+1 (or by one of the factors of B+1), the number itself is divisible by B+1 (or that factor). For B = 10, this holds for 11.

    E.g. 170138210 / 11 = 15467110 >> 1-7+0-1+3-8+2-1+0 = -11

  3. If K is a factor of B, then the number is divisible by K^n if and only if the last n digits of the number are divisible by K^n, where n is natural numbers (n = 1, 2, 3, ...). For B = 10, where factor(10) = 1, 2, 5, 10, this holds for 1 (trivial), 2, 4, 5, 8, 10, 25, .....

Adapted from http://www.derkeiler.com/Newsgroups/sci.crypt/2003-02/1039.html

No comments: