Divisibility Tests to 50 and Beyond

Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home

Divisibility Tests to 50 and Beyond
by Stephen D. T. Froggatt
Oaks Park High School, Ilford, Essex, UK

Back to Divisibility Rules

We know that to test for divisibility by (say) 15, we need only test for divisibility by 3 and 5. It follows that only the prime divisibility tests are required.

All the methods here work in the same recursive way. The number N1 is a multiple of prime P if (and only if) the smaller number N2 is also a multiple of P. These algorithms provide a way of reducing N1 to N2 (and N3, N4 etc.) until a multiple of P is recognised.

Some examples

We wish to test the number 742 (N1) for divisibility by 7. We get to the smaller number (N2) by chopping off the units digit, multiplying it by 5 and adding it to the number of tens in the orginal number (N1):

742 -> 74 + (2 x 5) = 84, which is clearly a multiple of 7

Therefore 742 is also a multiple of 7.

Another example. Is 3647 divisible by 7?

3647 -> 364 + (7 x 5) = 399

399 -> 39 + (9 x 5) = 84, which is a multiple of 7.

Therefore 3647 is also a multiple of 7 (and incidentally, so is 399).

I shall call this algorithm "Multiply by 5 and add".

The algorithm "Multiply by 2 and subtract" also works as a test for divisibility by 7:

3647 -> 364 - (7 x 2) = 350

350 -> 35 - (0 x 2) = 35, which is a multiple of 7

Therefore 3647 is also a multiple of 7 (and incidentally, so is 350).

These two algorithms form a "conjugate pair", one being "add" and the other being "subtract", as well as one being "multiply by m" and the other being "multiply by (p-m)", where p in this case is 7.

All this is leading up to the remaining divisibility tests. Each one uses the basic procedure of chopping off the units digit, multiplying it by m [or (p-m)] and then either adding to or subtracting from the truncated number.

Why These Methods Work

The simplest explanation, which is usually good enough for children, is that the procedure is just a fancy way of doing division by "chunking" - i.e., removing known multiples and just testing the remainder.

The Real Reason

The algorithm creates a smaller number that is a multiple of the prime being tested if and only if the original number was also a multiple. The explanation for the 7 test:

The original number (N1) can be written in the form 10a + b. For example, if N1 is 742 then a = 74 and b = 2.

Let's assume that 10a + b is a multiple of 7. Then 10a + b = 7k for some integer value of k.

Then b = 7k - 10a.

And a + 5b = a + 35k - 50a = 35k - 49a = 7 (5k - 7a)

So this is clearly a multiple of 7 as well.

The General Procedure

The trick is simply to find the multiplying factor (m) for each number (p) to be tested. Playing with the algebra reveals that m is simply the first integer for which 10m-1 is divisible by p. The conjugate factor (p-m) is similarly the first integer for which 10(p-m)+1 is divisible by p. This gives the following table:

Divisibility
Test (p)
Factor
(m)
Conjugate Factor
(p-m)
Best Algorithm
7 5 2 x5 and add
11 10 1 x10 and add
13 4 9 x4 and add
17 12 5 x5 and subtract
19 2 17 x2 and add
23 7 16 x7 and add
29 3 26 x3 and add
31 28 3 x3 and subtract
37 26 11 x11 and subtract
41 37 4 x4 and subtract
43 13 30 (either)
47 33 14 (either)
53 16 37 (either)

Let’s use the table to test whether 3534 is divisible by 31. The algorithm is "Multiply by 3 and subtract":

3534 -> 353 - (4 x 3) = 341

341 -> 34 - (1 x 3) = 31 which is a multiple of 31

Therefore 3534 is divisible by 31.