Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
Middle School Division

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search