Tuesday, 17 April 2012

Divisibility Testing

We all know divisibility tests for simple numbers like 2,3,4.etc but here 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.

The Rule of 11
Let us first try out divisibility by 11 rule.

The first glance may force you to think that this method is complicated, but little time getting familiar with it, would make your life very simple.

For testing 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.


Let us understand this with the example of 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.

The Rule of 7

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 (2x17) = 14,250

1,425 + 85 (5x17) = 1,510

151 - 51 (3x17) = 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 an interesting number with connections to the number 7, which we shall discuss in a later post. However, 142,857 itself is not divisible by 7.

This rules are based on simple mathematical rules extrapolated to come up with a solution easier and practical for day to day issues. I hope you enjoyed knowing this!

1 comment:

  1. Thanks. Great blogs. For best vedic math solution please visit http://help-homework-math.com/