Finding Divisibility Rules for Large Numbers

Date: 12/21/2000 at 00:31:35
From: David
Subject: Seeking out divisibility rules

Is there any way to systematically find divisibility rules for any 
number n, where n > 10?

Date: 12/21/2000 at 11:40:03
From: Doctor Rob
Subject: Re: Seeking out divisibility rules

Thanks for writing to Ask Dr. Math, David.

Yes, there is a way. First of all, factor n into its prime power 
divisors:

     n = p1^e1 * p2^e2 * ... * pr^er.

A number is divisible by n if and only if it is divisible by each 
prime power in this expression. That reduces the problem to one where 
n is a prime power.

A number is not divisible by a prime power p^e if it is not divisible 
by the prime p itself, so a necessary but not sufficient condition is 
divisibility by p. If the number is divisible by p, you can divide it 
out, and see if the quotient is divisible by p^(e-1). That will reduce 
the problem to one where n is a prime number p.

One way to find a test for divisibility by p is to find the smallest 
multiple of p of the form x*10^k + 1 or x*10^k - 1, where x is very 
small (preferably one digit). Then the test is that N is divisible by 
p if and only if the number gotten from N by chopping off the last k 
digits, multiplying them by x, and subtracting (or adding, 
respectively) that product to the rest of N, is divisible by p.

For example, if you want to test divisibility by 107, you might find 
that 107 is a factor of 1899999, so you can test for divisibility by 
chopping off the last five digits, multiplying that by 19, and adding 
that product from the rest of the digits of N. The result will be 
divisible by 107 if and only if the N is. You can continue this until 
the number has at most five digits, then you have to try dividing by 
107 directly.

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

Date: 12/21/2000 at 13:35:00
From: Doctor Greenie
Subject: Re: Seeking out divisibility rules

Yes, there is.

I'm not sure I could provide a rigorous mathematical justification for 
the method, so I'll just demonstrate it for a few cases.

The method for any given n is based on the pattern of remainders 
formed when successive powers of 10 are divided by n.  The method is 
best demonstrated by examples; however, here is an attempt to put the 
method in words:

To determine whether a number is divisible by n, proceed as follows:

(1) Multiply each digit in the 10^i column by the remainder when 
    10^(i+1) is divided by n.

(2) Add all the numbers obtained in step (1).

(3) The original number is divisible by n if and only if the number 
    obtained in step (2) is divisible by n

Let's first use this method to derive the familiar divisibility rule 
for 3. We start by finding the remainders when successive powers of 10 
are divided by 3, until a pattern is found:

     power of 10   remainder when divided by 3
     -----------   ---------------------------
        10^1          1
        10^2          1
        10^3          1
         :            :

Here the pattern emerges immediately: every power of 10 leaves a 
remainder of 1 when divided by 3. The rule that comes out of this 
method is as follows:

   "a number is divisible by 3 if (and only if) the number (1*units 
   digit + 1*tens digit + 1*hundreds digit + ...) is divisible by 3"

This is equivalent to the familiar rule that a number is divisible by 
3 if and only if the sum of its digits is divisible by 3. (This method 
quickly obtains the corresponding familiar rule for divisibility by 9, 
since every power of 10 also leaves a remainder of 1 when divided by 
9.)

Perhaps you are familiar with the divisibility rule for 11: find the 
sum of the digits in the odd-numbered locations and the sum of the 
digits in the even-numbered locations and take the difference; if the 
difference is divisible by 11, then the original number is. Let's see 
if we can develop that rule using this method:

     power of 10   remainder when divided by 11
     -----------   ----------------------------
        10^1          10
        10^2           1
        10^3          10
        10^4           1
        10^5          10
         :             :

We can use a "trick" here to simplify our divisibility rule a bit. 
Wherever the remainder upon dividing by 11 is 10, we can also say the 
"remainder" is -1. Then our table looks like this:

     power of 10   remainder when divided by 11
     -----------   -----------------------------
        10^1          -1
        10^2           1
        10^3          -1
        10^4           1
        10^5          -1
         :             :

And from this we can see how, using our method, we can get the 
familiar divisibility rule for 11.

Now let's use the method to obtain a divisibility rule for 7.

     power of 10   remainder when divided by 7
     -----------   ---------------------------
        10^1          3
        10^2          2
        10^3          6  (or -1)
        10^4          4  (or -3)
        10^5          5  (or -2)
        10^6          1
        10^7          3
        10^8          2
        10^9          6  (or -1)
         :            :

Without trying to put the rule into words, let's use it in an example. 
The number 5497756005 is divisible by 7. We can show this is so using 
our divisibility rule as follows:

       (5*3)+(0*2)+(0*6)+(6*4)+(5*5)+(7*1)+(7*3)+(9*2)+(4*6)+(5*4)
     = 15 + 0 + 0 + 24 + 25 + 7 + 21 + 18 + 24 + 20
     = 154

and 154 is divisible by 7, so 5497756005 is also.

Note carefully how this sum of 154 was obtained. In the string of 
products that were added to get the total of 154, the first digit in 
each product is a digit of the number whose divisibility is being 
checked, starting with the units digit and moving left; and the second 
digit in each product is the remainder when successive powers of 10 
are divided by 7, starting with 10^1 for the units digit.

Here's another example, to find a divisibility rule for 13.

     power of 10   remainder when divided by 13
     -----------   ----------------------------
        10^1          10  (or -3)
        10^2           9  (or -4)
        10^3          12  (or -1)
        10^4           3
        10^5           4
        10^6           1
        10^7          10  (or -3)
        10^8           9  (or -4)
        10^9          12  (or -1)
         :             :

The number 3266497 is divisible by 13. We can show this is so using 
our divisibility rule as follows:

       (7*10) + (9*9) + (4*12) + (6*3) + (6*4) + (2*1) + (3*10)
     = 70 + 81 + 48 + 18 + 24 + 2 + 30
     = 273

and 273 is divisible by 13, so 3266497 is also.

Or we could keep the numbers smaller by using the negative remainders:

       (7*-3) + (9*-4) + (4*-1) + (6*3) + (6*4) + (2*1) + (3*-3)
     = (-21) + (-36) + (-4) + 18 + 24 + 2 + (-9)
     = -26

It can be interesting to see what kinds of rules result from using 
this method on numbers for which we already have divisibility rules. 
Consider the rule which results for divisibility by 6:

     power of 10   remainder when divided by 6
     -----------   ---------------------------
        10^1          4
        10^2          4
        10^3          4
        :             :

Here the divisibility rule says a number is divisible if 4 times the 
sum of all the digits is divisible by 6. This is equivalent to saying 
that it is divisible by 6 if twice the sum of the digits is divisible 
by 3. And that is equivalent to the divisibility rule you are probably 
familiar with - that a number is divisible by 6 if it is divisible by 
both 2 and 3.

So...

You CAN get divisibility rules for any number... but most of them are 
much harder to use than long division (or other hand methods). And in 
this day of calculators, the divisibility rules are useless except as 
a mathematical exercise.

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