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

### 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,
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

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/
```
Associated Topics:
High School Number Theory

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