Divisibility Tests in Different Bases

Date: 11/16/2008 at 03:52:20
From: Mia
Subject: Divisibility tests in different base-systems

How do I determine the divisibility test for 7 in the base-nine 
system? 

So far, I created a multiplication chart for base-nine and found that 
compared to the base-ten system, its

Base 10     Base 9
 7            7
14           15
21           23
28           31
35           38
42           46
49           54
56           62
63           70

and notice that the number in the base 9 column increased by 1 except 
the fourth and fifth numbers. 

I also divided the numbers because I was also looking for a 
divisibility test for 3.  So, now I have no idea how to find the test
for 7.

Date: 11/17/2008 at 00:23:39
From: Doctor Greenie
Subject: Re: Divisibility tests in different base-systems

Hi, Mia --

A very interesting question!  In preparing an answer, I have learned a
lot more than I previously knew about divisibility rules (and I 
thought I knew a lot before this...!)

This answer will be quite lengthy, showing three algorithms of very 
different types for testing for divisibility by 7.  For a better 
understanding of the three different algorithms, we will first look 
at them with a base 10 number; then we will tackle the algorithms in 
base 9.

For my demonstrations I will use the following number which is 
divisible by 7:

  3929625 (base 10) = 7348380 (base 9)

I will provide references in the Dr. Math archives for all three of 
the algorithms I discuss.  Consult those references if you have any 
questions about the contents of my message.


I-a. The first algorithm; in base 10....

For this first algorithm, I provide the following reference in the 
Dr. Math archives:

  Finding Divisibility Rules for Large Numbers
    http://mathforum.org/library/drmath/view/55962.html 

This method uses the values of powers of 10, modulo 7, to create a 
numerical expression from the given number; the given number is 
divisible by 7 if and only if the simplified expression is divisible 
by 7.  The powers of 10, modulo 7, form the following repeating 
sequence:

  3, 2, -1, -3, -2, 1, (repeat...)

The expression we build, using these modulo 7 numbers and the digits 
of the original number--as explained on the referenced page--is

  5(3) + 2(2) + 6(-1) + 9(-3) + 2(-2) + 9(1) + 3(3)

This expression simplified is

  15 + 4 - 6 - 27 - 4 + 9 + 9 = 0

Because 0 is divisible by 7, the original number is divisible by 7.

General comments on this first method when in base 10:

  (1) It seems a bit like magic; it is difficult to understand why it 
      works.
  (2) It is slow, with a great deal of sometimes difficult
      computation required--determining the repeating sequence of 
      values of the powers of 10 modulo 7; and then forming and 
      simplifying the long expression using those values and the
      digits of the given number....


II-a.  The second algorithm, in base 10....

For this second algorithm, I provide the following reference in the 
Dr. Math archives:

  Divisibility Tests to 50 and Beyond
    http://mathforum.org/dr.math/faq/faq.divisibleto50.html 

(For any attempt to understand how this algorithm (in two varieties) 
is derived, refer to the given reference.)

To begin using this algorithm, we find the smallest integer m for 
which 10m-1 is divisible by 7; we find it to be m = 5.  Then the 
algorithm for testing for divisibility by 7 in base 10 is

  1. remove the last digit of the number, multiply it by 5, and add
     it to the number that remains;
  2. repeat as necessary until the remaining number is recognizable
     as being divisible by 7

I hope you can follow the calculations below that demonstrate that my 
example base 10 number is divisible by 7, using this algorithm:

Remember my original base 10 number is 3929625.  Using this second 
algorithm, we find

      3929625 (remove 5, multiply it by 5, and add to remaining #)
        + 25
      ------
      392987  (remove 7, multiply it by 5, and add to remaining #)
       + 35
      -----
      39333
      + 15
      ----
      3948
     + 40
     ----
      434
    + 20
    ----
      63

We know that 63 is divisible by 7; that means our original number is 
also divisible by 7.

With the other version of this algorithm, instead of multiplying the 
last digit by 5 and adding, we multiply it by 2 (because 7-5=2--see 
the referenced page in the archives) and subtract.  Here is this 
alternative form of this second algorithm to again show my example 
number is divisible by 7:

     3929625  (remove 5, multiply it by 2, and subtract from #)
       - 10
     ------
     392952   (remove 2, multiply it by 2, and subtract from #)
       - 4
     -----
     39291
      - 2
     ----
     3927
    - 14
     ---
     378
   - 16
     --
     21

We know that 21 is divisible by 7; that means our original number is 
also divisible by 7.

General comments on this second method when in base 10:

  (1) It too seems like magic, since it is difficult to understand why
      it works.
  (2) On the other hand, with a little practice, the actual use of 
      the process requires calculations that are far easier than with
      the first algorithm.  


III-a.  The third algorithm, in base 10....

For this third algorithm, I provide the following reference in the 
Dr. Math archives:

  Divisibility Algorithm
    http://mathforum.org/library/drmath/view/58516.html 

This algorithm really does not require a reference.  It is easy to 
explain the method; and it is easy to understand why the method works.

With this method, we simply add or subtract multiples of our divisor 
to the number we are working with to obtain trailing zeros, and then 
we simply drop those trailing zeros, since trailing zeros don't 
affect the divisibility of a number.

Here is a demonstration of the use of this third algorithm to verify 
that our example number is divisible by 7:

  3929625 + 35 = 3929660 --> 392966
  392966 + 14 = 392980 --> 39298
  39298 - 28 = 39270 --> 3927
  3927 - 7 = 3920 --> 392
  392 + 28 = 420 --> 42

We know 42 is divisible by 7, so our original number is divisible by 
7.

General comments on this third method when in base 10:

  (1) It is easy to understand why it works.
  (2) The actual steps required are far easier than either of the
      other methods.
  (3) The calculations required are far easier than either of the 
      other methods.


NOW....  Let's look at these three different algorithms for checking 
for the divisibility of a number by 7 if we are working in base 9....

Remember that my example number, 3929625 in base 10, is 7348380 in 
base 9....


I-b. The first algorithm; in base 9....

Because we are now in base 9, this method is going to be based on the 
values of the powers of 9, modulo 7 (not values of the powers of 10, 
modulo 7).  In base 9, the powers of 9, modulo 7, form the following 
repeating sequence:

  2, 4, 1, (repeat...)

The expression we build, using these modulo 7 numbers and the digits 
of the original number--as explained on the referenced page--is

  0(2) + 8(4) + 3(1) + 8(2) + 4(4) + 3(1) + 7(2)

This expression simplified is

  0 + 32 + 3 + 16 + 16 + 3 + 14 = 84

Because 84 is divisible by 7, the original number is divisible by 7.

General comments on this first method when in base 9:

  (1) It still seems a bit like magic; it is difficult to understand 
      why it works.
  (2) It is slow, with a great deal of sometimes difficult 
      computation required--determining the repeating sequence of
      values of the powers of 9 modulo 7; and then forming the long
      expression using those values and the digits of the given 
      number....
  (3) On the other hand, all the actual calculations for this method
      are performed in base 10.


II-b.  The second algorithm, in base 9....

Similar to when working in base 10, to begin using this algorithm in 
base 9, we find the smallest integer m for which 9m-1 (not "10m-1") 
is divisible by 7; we find m=4.  Then the algorithm for testing for 
divisibility by 7 in base 10 is

  1. remove the last digit of the number, multiply it by 4, and add
     it to the number that remains;
  2. repeat as necessary until the remaining number is recognizable
     as being divisible by 7

Again I hope you can follow the calculations below that demonstrate 
that my example base 9 number is divisible by 7, using this 
algorithm.  The process is complicated by the fact that we are now 
performing arithmetic (addition or subtraction) in base 9.

Remember my original base 9 number is 7348380.  Using this second 
algorithm, and doing our arithmetic in base 9, we find

     7348380  (remove 0, multiply it by 4, add to remaining #)
        + 0
     ------
     734838   (remove 8, multiply it by 4, convert 32 to 35 in
      + 35     base 9, add to remaining #)
     -----
     73528
     + 35
     ----
     7387
    + 31
     ---
     770
    + 0
     --
     77
  + 31
    --
    38

We have had to perform single-digit base 9 multiplication and base 9 
addition to get to this point; now we have to do some evaluation of 
the number "38" base 9 to see if it is divisible by 7.  "38" base 9, 
converted to base 10, is 3(9) + 8(1) = 35, which is divisible by 7.

So we know that 38 (base 9) is divisible by 7; that means our 
original number is also divisible by 7.

With the other version of this algorithm, instead of multiplying the 
last digit by 4 and adding, we multiply it by 3 (because 7-4=3--see 
the referenced page in the archives) and subtract.  Here is this 
alternative form of this second algorithm to again show my example 
number is divisible by 7:

     7348380
        - 0
     ------
     734838   (remove 8, multiply by 3, turn 24 into 26 in base
      - 26    (nine, subtract from remaining #)
     -----
     73456
     - 20
     ----
     7325
    - 16
     ---
     715
   - 16
     --
     54

This number, 54 in base 9, converted to base 10 is 5(9) + 4(1) = 49.

We know that 49 is divisible by 7; that means our original number is 
also divisible by 7.

General comments on this second method when in base 9:

  (1) It too still seems like magic, since it is difficult to  
      understand why it works.
  (2) The actual calculations required are HARDER when in base 9, 
      because we need to perform multiplication and addition (or, 
      even worse, subtraction) in base 9 with this method.


III-b.  The third algorithm, in base 9....

As when in base 10, with this method, we simply add or subtract 
multiples of our divisor to the number we are working with to obtain 
trailing zeros, and then we simply drop those trailing zeros, since 
trailing zeros don't affect the divisibility of a number.  But now 
the arithmetic must be performed in base 9....

Following is a demonstration of the use of this third algorithm to 
verify that our example number is divisible by 7.  We will need (for 
quick reference) the list of multiples of 7 you found for base 9:

  7*1 =  7
  7*2 = 15
  7*3 = 23
  7*4 = 31
  7*5 = 38
  7*6 = 46
  7*7 = 54
  7*8 = 62

  7348380 -->  734838
  734838 + 31 = 734870 --> 73487
  73487 + 62 = 73550 --> 7356
  7356 + 23 = 7380 --> 738
  738 + 31 = 770 --> 77
  77 + 62 = 150 --> 15

From our list of multiples of 7, we know 15 (base 9) is divisible by 
7, so our original number is divisible by 7.

General comments on this third method when in base 10:

  (1) It is easy to understand why it works.
  (2) The actual steps required are far easier than either of the 
      other methods.
  (3) The calculations required must be performed in base 9; overall,
      however, this third method is still much easier than the first 
      method.


I hope at least some of all this is understandable to you.

I have long held the opinion that the third method described above 
is far more practical than either of the other methods when in base 
10.  Having now investigated--in response to your question--methods 
for testing divisibility in other bases, I firmly believe that the 
third method is far more practical in any base.

Another advantage of the third method, not seen in the above 
discussion since I was only addressing divisibility by a single 
number (7), is that it can easily be applied for ANY divisor--whereas 
for each of the other methods the details of the process are 
completely different for different divisors.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/