Divisibility Testing, Part 003

The first two parts of my article dealt with tests for divisibility by the common numbers 2, 3, 4, 5, 6, 8, 9 and 10. In the previous articles we saw how to test for divisibility by 3, 6 or 9 by examining the sum of all the digits of a number, and what to look for when testing for divisibility by 2, 4 and 8.

In this final part of my article I wish to demonstrate how to test for divisibility by 7, 11 and by higher prime numbers such as 13, 17, 19 and so on.

We shall begin with testing for divisibility by 11. The procedure appears complicated at first, but once you know what to do, you will be surprised how simple it actually is.

To test that a number is divisible by 11, add up two separate numbers. The first sum comprises the sum of the digits of the odd numbered columns of the number (1st, 3rd, 5th and so on). The second comprises the sum of the digits of the even numbered columns of the number (2nd, 4th, 6th and so on).

If the difference between these two numbers is zero, 11 or a multiple of 11, the number is divisible by 11.

As our only example in this part of the article, I choose to focus entirely upon one number: 142,857.

Here, we now test 142,857 for divisibility by 11.

1 + 2 + 5 = 8
4 + 8 + 7 = 19

19 – 8 = 11

142,857 is divisible by 11.

So that’s almost all the lowest prime and non-prime factors from 2 through to 11 covered.

So now we come to the divisibility test for the only number remaining, 7. When using this test, which can be applied to any other prime number, you only need to know the multiples of the candidate factor from zero and the factor itself through to five times the factor.

For example, in working out how to divide a number by 7, you only need to know 0, 7, 14, 21, 28 and 35. If you are testing for divisibility by 13, you only need to know 0, 13, 26, 39, 52 and 65.

The working behind this method is outlined below.

First of all, if a number a is a multiple of x:-

a = n1x

then any multiple b of a is also going to be a multiple of x:-

b = n2a ==> b = n2n1x

Next, any integer above 1 can be shown to be the sum of two smaller integers:-

c = d + e (d < c; e < c; d > 0; e > 0).

If we know that one of these two right hand terms is a known integer multiple of the candidate factor, we can eliminate it and test for divisibility with the smaller term, For example, substitute b for d:-

c = n2a + e

e = c – n2a

If, when we test e, we discover that it too is a multiple of x:-

e = n3x

we can deduce that the whole number c must be divisible by x.

This is the test: by eliminating known multiples of the candidate factor, if we obtain a final residue of 0 or the candidate factor, the number is divisible by the candidate factor.

To test this, we once again turn back to 142,857 and test it to see if it is divisible by 7. We already know that 142,857 is divisible by 11.

We can begin by eliminating the easiest multiples of 7. When eliminating a multiple, do not be afraid to take big bites.

142,857 – 140,000 = 2,857

2,857 – 2,800 = 57

Since the nearest multiple of 7 is now 56, eliminating that yields the final residue, 1. So 142,857 is not divisible by 7.

Let us test for divisibility by another prime factor, namely 17.

142,857 – 17 = 142,840

14,284 – 34 (2×17) = 14,250

1,425 + 85 (5×17) = 1,510

151 – 51 (3×17) = 100

100 – 85 = 15

Since the residue is neither 0 nor 17, 142,857 is not divisible by 17.

This technique can be applied to divisibility tests by any prime factor, and all it requires is the knowledge of the multiples of the candidate factor from 0 to 5x the factor.

Before wrapping up this article, I will conclude my business with 142,857. In my analysis of the candidate factors which go into 142,857 I determined that this number has the following factors, and only these factors:=

142,857 = 3 x 3 x 3 x 11 x 481

142,857 is a remarkable number with some interesting connections to the number 7, which I shall elaborate upon in a later post. However, 142,857 itself is not divisible by 7: a rare demonstration that proves that mathematics is not immune to sharing a little irony with us mere mortals.

Divisibility by a candidate factor is, of course, the primary means of testing to see if a number is a prime number or factorisable. It is a useful tool to know, not least because it is the most efficient tool you can use to verify that your arithmetical computations are correct.

I hope that this examination of divisibility by candidate factors has given you one more helpful navigational tool to help steer your course along this great mathematical Odyssey which we all share.

– The Vedic Maths Forum India