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

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/
```
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