Divisibility Rule for All Divisors

Date: 11/07/1999 at 22:13:17
From: Jonathan Y Chung
Subject: Number Theory

I heard from a friend that there exists a theorem that you can use to 
figure out divisibility rules for all natural numbers. Is there such a 
theorem? If it exists, could you tell me the name of it?

Thanks,
Jonathan

Date: 12/31/1999 at 09:01:38
From: Doctor TWE
Subject: Re: Number Theory

Hi Jonathan,

I don't know of a specific theorem, but I have made some observations 
about the divisibility rules. All the divisibility rules deal with the 
relation of the divisor number and 10. Let's look at some examples:

2 and 5: Since these are divisors of 10, all multiples of 10 are 
divisible and you only have to check the last digit.

4, 8, 16, ... and 25, 125, 625, ...: These are powers of 2 (4 = 2^2, 
8 = 2^3, etc.) and powers of 5 (25 = 5^2, 125 = 5^3, etc.) Since each 
power of 10 is divisible by the same power of 2 or 5, we only have to 
check the last n digits (where n is the power of 2 or 5.) For example, 
to see if a number is divisible by 8 (8 = 2^3) we check to see if the 
last three digits are divisible by 8. Likewise, to see if a number is 
divisible by 25 (25 = 5^2) we only have to check whether the last two 
digits are divisible by 25.

3 and 9: 10 divides by 3 or 9 with a remainder of 1 (we call it 
"modulo 1"). So every multiple of 10 has a remainder of 1. Likewise 
100 is 99+1, 1000 is 999+1, etc. We can "cast out" the 9's, 99's, 
999's etc. and just count the "remainder 1's." That's why you just add 
up the digits. Every digit is the number of "remainder 1's."

7: There are two alternate methods; one follows the pattern I'm 
building up to. That method is as follows: beginning with the leftmost 
digit, take the total, triple it, and add the next digit. For example, 
with 1834 we'd start with 1*3 = 3, then add 3+8 = 11, triple that for 
11*3 = 33, then add 33+3 = 36, triple that for 36*3 = 108, then add 
108+4 = 112. If we weren't sure that 112 was divisible by 7 we could 
repeat the process: 1*3 = 3, 3+1 = 4, 4*3 = 12, 12+2 = 14. (We should 
recognize that 14 is divisible by 7.)

Why does this work? Because 10 = 7+3. So for each 10 we have in the 
number, we can "cast out" 7 and keep the "remainder 3," which we add 
to the ones digit. For multiples of 10, we have to keep each 
"remainder 3," which is why we multiply by 3. 100 is 70 + 30, so for 
each 100 we "cast out" 70 and add each "remainder 30" as +3 to the 
tens digit (again, we need to multiply the hundreds digit by 3 to 
account for every "remainder 30" we had).

11: For 11, we alternately add and subtract digits from left to right. 
Why? Because 10 = 11 - 1. Every 10 is one short of an 11, so we 
subtract 1 for each group of ten from the units. If we have hundreds, 
we subtract 1 for each group of 100 from the tens, etc. Technically, 
this means we should start by subtracting the leftmost digit, then 
adding the next, etc., but it doesn't matter in this case. The answer 
will have the same magnitude, just the opposite sign.

To formalize this (and make it fit with the generalization I'm leading 
up to), we begin with the leftmost digit, multiply the total by -1, 
then add the next digit; repeating until we get to the units digit. If 
the result is a multiple of 11 (positive, negative or zero), so was 
the original number.

13: Since 10 = 13-3, we can start with the leftmost digit, multiply 
the total by -3, and add the next digit. For example, for 1859 we get: 
1*(-3) = -3, -3+8 = 5, 5*(-3) = -15, -15+5 = -10, -10*(-3) = 30, 
30+9 = 39; which is a multiple of 13, so 1859 is a multiple of 13. As 
with 7, there are other methods that I'm overlooking because they 
don't fit the generalization below.

6, 12, 14, 15, etc.: Since these are composite numbers, we just have 
to check for divisibility by all of their factors (2 and 3 for 6, 4 
and 3 for 12, 2 and 7 for 14, etc.)

Looking at 7, 9, 11 and 13, we can develop a general rule as follows: 
First, determine the "multiplier" (call it m) by subtracting the 
divisor from 10. Next, beginning with the leftmost digit, multiply the 
total by m and add the next digit (from left to right) until all 
digits have been added. If the result is divisible by the divisor, so 
was the original number.

Let's try this with a test case. Suppose we wanted to see whether 
715343 is divisible by 17. First, we let m = 10 - 17 = -7. Then we 
apply the rule from left to right (to save space, I'll do each 
multiply-and-add in one step):

         7*(-7)+1 = -48
       -48*(-7)+5 =  341
       341*(-7)+3 = -2384
     -2384*(-7)+4 =  16692
     16692*(-7)+3 = -116841

But is -116841 divisible by 17? We'll apply the rule again to this 
result. We can ignore the (-) at the beginning (if -x is divisible by 
y, so is x divisible by y):

        1*(-7)+1 = -6
       -6*(-7)+6 =  48
       48*(-7)+8 = -328
     -328*(-7)+4 =  2300
     2300*(-7)+1 = -16099

Here we go again. See whether 16099 is divisible by 17:

       1*(-7)+6 = -1
      -1*(-7)+0 =  7
       7*(-7)+9 = -40
     -40*(-7)+9 =  289

If we don't know that 289 = 17^2, we can apply the rule one more time:

      2*(-7)+8 = -6
     -6*(-7)+9 = 51

which is 17*3. So our rule says that 715343 IS divisible by 17. 
Checking by calculator, 715343/17 = 42079 exactly.

As you can see, when our multiplier is close to 10, it doesn't reduce 
the number much, and we have to repeat the process many times before 
we get something reasonable to check by hand.

This rule won't work with divisors larger than 20 because the 
magnitude of the multiplier would be larger than 10, so we'd be making 
larger numbers to check instead of smaller ones. Can you see a way to 
extend the generalized rule for divisors larger than 20?

To see why other divisibility methods work, check out Divisibility 
Rules from the Dr. Math FAQ and our Math Tips and Tricks page:

  http://mathforum.org/dr.math/faq/faq.divisibility.html   
  http://mathforum.org/k12/mathtips/division.tips.html#divide13   

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